题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=2063
解题思路
匈牙利算法,二分图模板
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
int vis[N], e[N][N], p[N];
int k, m, n;
bool find(int x) {
for(int i = 1;i <= n;i ++) {
if(e[x][i] && !vis[i]) {
vis[i] = 1; // 置一
if(p[i] == 0 || find(p[i])){
p[i] = x;
return true;
}
}
}
return false;
}
int main()
{
while(~scanf("%d", &k), k) {
scanf("%d%d", &m, &n);
int x, y, ans = 0;
memset(e, 0, sizeof e);
memset(p, 0, sizeof p);
for(int i = 0;i < k;i ++) scanf("%d%d", &x, &y), e[x][y] = 1; // 存单边
for(int i = 1;i <= m; i++) {
memset(vis, 0, sizeof vis); // 每次都要重置
if(find(i)) ans ++;
}
printf("%d\n", ans);
}
return 0;
}