poj 1274The Perfect Stall

时间:2024-01-16 10:37:08

第一次接触二分图匹配。

这题是一个匈牙利算法的模板题直接套即可。

题意是  给你奶牛和谷仓的个数a和b,接下来a行是奶牛喜欢去的谷仓。第一个是谷仓个数,接下来是谷仓编号。

这里我们把行当奶牛,列当谷仓。

在套模板。

。ok;

#include<Stdio.h>
#include<string.h>
int map[1005][1005];
int a,b,link[1005],use[1005]; int dfs(int cap)
{
int i,j;
for(i=1;i<=b;i++)
{
if(map[cap][i]&&!use[i])
{
use[i]=1;
j=link[i];
link[i]=cap;
if(j==-1||dfs(j))
return 1;
link[i]=j;
}
}
return 0;
} int hungary()
{
int num=0;
int i,j;
memset(link,-1,sizeof(link));
for(i=1;i<=a;i++)
{
for(j=1;j<=b;j++)
{
use[j]=0;
}
if(dfs(i))
num++;
}
return num;
}
int main()
{
int i,j,c,d;
while(~scanf("%d %d",&a,&b))
{
memset(map,0,sizeof(map));
for(i=1;i<=a;i++)
{
scanf("%d",&c);
for(j=1;j<=c;j++)
{
scanf("%d",&d);
map[i][d]=1;
}
}
printf("%d\n",hungary());
}
return 0;
}