HDU 1083 网络流之二分图匹配

http://acm.hdu.edu.cn/showproblem.php?pid=1083

二分图匹配用得很多

这道题只需要简化的二分匹配

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxm 410
using namespace std;
int p,n;
int master[maxm];
int linking[maxm][maxm];
int has[maxm];
int solve(int x)//x课
{
int i;
for(i=;i<=n;i++)
{
if(linking[x][i]&&!has[i])
{
has[i]=;
if(!master[i]||solve(master[i]))
{
master[i]=x;
return ;
}
}
}
return ;
}
int main()
{
int m,sum=;
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&p,&n);
memset(master,,sizeof(master));
memset(linking,,sizeof(linking));
for(int i=;i<=p;i++)
{
int course;
int student;
scanf("%d",&course);
for(int j=;j<=course;j++)
{
scanf("%d",&student);
linking[i][student]=;
}
}
for(int donser=;donser<=p;donser++)
{
memset(has,,sizeof(has));
if(solve(donser)) sum++;
}
if(sum==p) printf("YES\n");
else printf("NO\n");
sum=;
}
return ;
}
上一篇:js变量类型和计算


下一篇:深入学习webpack(一)