题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=2063

女生为X集合,男生为Y集合,求二分图最大匹配数即可。

 #include<cstdio>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<stdbool.h>
#include<time.h>
#include<stdlib.h>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
using namespace std;
#define clr(x,y) memset(x,y,sizeof(x))
#define sqr(x) ((x)*(x))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define LL long long
#define INF 0x3f3f3f3f
#define A first
#define B second
#define PI acos(-1.0)
const int N=+;
int n,m,k,f[N],g[N][N],link[N]; void init()
{
clr(f,);
clr(g,);
clr(link,-);
} bool find(int x)
{
for(int i=;i<=n;i++) {
if(!f[i] && g[x][i]) {
f[i]=;
if(link[i]==- || find(link[i])) {
link[i]=x;
return true;
}
}
} return false;
} int hungary()
{
int ans=;
for(int i=;i<=m;i++) {
clr(f,);
if(find(i)) ans++;
}
return ans;
} int main()
{
int u,v,k; while(~scanf("%d",&k)) {
if(!k) break;
init();
scanf("%d%d",&m,&n);
while(k--) {
scanf("%d%d",&u,&v);
g[u][v]=;
}
printf("%d\n",hungary());
} return ;
}
04-12 22:50