链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1083
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82834#problem/C
一共有N个学生跟P门课程,一个学生可以任意选一
门或多门课,问是否达成:
1.每个学生选的都是不同的课(即不能有两个学生选同一门课)
2.每门课都有一个代表(即P门课都被成功选过)
现想组建一个委员会,委员会中的每个学生都要代表不同的课程,且每个课程都有它的代表。
算法分析:这正符合二分图最大匹配的条件。把课程作为二分图中X节点集合,得到最大匹配,如果匹配数等于课程数,则匹配与Y集合的交集,就可看成是这样一个委员会,则输出YES,否则,输出NO。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 305
#define INF 0x3f3f3f3f int n, m, un, vn, G[N][N], used[N], p[N]; int Find(int u)
{
for(int i=; i<=vn; i++)
{
if(G[u][i] && !used[i])
{
used[i] = ;
if(p[i]==- || Find(p[i]))
{
p[i] = u;
return ;
}
}
}
return ;
} int hungary() //匈牙利算法
{
int ans = ;
memset(p, -, sizeof(p)); for(int i=; i<=un; i++)
{
memset(used, , sizeof(used));
if(Find(i)) ans++;
}
return ans;
} int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int i, j, v, k; scanf("%d%d", &n, &m); memset(G, , sizeof(G));
for(i=; i<=n; i++)
{
scanf("%d", &k);
for(j=; j<=k; j++)
{
scanf("%d", &v);
G[i][v] = ;
}
} un = n;
vn = m; if(un==hungary()) printf("YES\n");
else printf("NO\n");
}
return ;
}
傻傻的刷题,加油!