文章

25

粉丝

0

获赞

0

访问

68549

头像
二分图匹配-車的位置
经验总结
发布于2020年4月17日 00:22
阅读数 2484

将行作为一个集合,将列作为另一个集合,进行二分图匹配,匹配数即匹配的边作为車的位置。

#include<iostream>
using namespace std;
const int N = 210;
int g[N][N], match[N], n, m, t;
bool st[N];
bool find(int x){
	for (int i = 1; i <= m; i++){
		if (st[i] || g[x][i]){
			continue;
		}
		st[i] = true;
		if (!match[i] || find(match[i])){
			match[i] = x;
			return true;
		}
	}
	return false;
}
int main(){
	cin >> n >> m >> t;
	for (int i = 1; i <= t; i++){
		int x, y;
		cin >> x >> y;
		g[x][y] = 1;
	}
	int ans = 0; 
	for (int i = 1; i <= n; i++){
		memset(st, false, sizeof(st));
		if (find(i)){
			ans++;
		}
	}
	cout << ans << endl;
	system("pause");
	return 0;
}

 



登录后发布评论

暂无评论,来抢沙发