题目：http://acm.hdu.edu.cn/showproblem.php?pid=2063
又是一道二分图匹配的裸题，直接上匈牙利算法
注意一点它末尾的0结束，是标志着有多组数据……坑……
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<queue>
#define fre(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
#define Test1 freopen("in.in","r",stdin);freopen("1.out","w",stdout)
#define Test2 freopen("in.in","r",stdin);freopen("2.out","w",stdout)
using namespace std;
typedef long long LL;
typedef double db;
const double CPS=CLOCKS_PER_SEC,TL=0.98;
const int oo=,N=,M=;
int first[N],Next[M],v[M],g[N];
bool f[N];
inline bool xyl(int x)
{
int i,k;
for (i=first[x];i;i=Next[i])
{
k=v[i];
if (f[k])
{
f[k]=;
if ((!g[k])||xyl(g[k]))
{
g[k]=x;
return ;
}
}
}
return ;
}
int main()
{
int n,na,nb,i,j,ans,x;
scanf("%d",&n);
while (n)
{
ans=;
scanf("%d%d",&na,&nb);
for (i=;i<=na;i++) first[i]=;
for (i=;i<=nb;i++) g[i]=;
for (i=;i<=n;i++)
{
scanf("%d%d",&x,&v[i]);
Next[i]=first[x];
first[x]=i;
}
for (i=;i<=na;i++)
{
for (j=;j<=nb;j++) f[j]=;
if (xyl(i)) ans++;
}
printf("%d\n",ans);
scanf("%d",&n);
}
return ;
}
版权所有，转载请联系作者，违者必究