题目:http://acm.hdu.edu.cn/showproblem.php?pid=1083
二分图的最大匹配。。直接用套用匈牙利算法即可。
下面是AC代码:
#include<cstdio> #include<cstring> using namespace std; const int maxn = 110; bool g[3*maxn][3*maxn]; int match[3*maxn]; bool vis[3*maxn]; int p,n; bool dfs(int cur){ for(int i=1;i<=n;i++){ if(g[cur][i]==true&&!vis[i]){ vis[i]=true; int t=match[i]; if(t==-1||dfs(t)){ match[i]=cur; return true; } } } return false; } int hungary(){ int res=0; for(int i=1;i<=n;i++) match[i]=-1; for(int i=1;i<=p;i++){ memset(vis,false,sizeof(vis)); if(dfs(i)) res++; } return res; } int main(){ int t,num,a; scanf("%d",&t); while(t--){ scanf("%d%d",&p,&n); memset(g,false,sizeof(g)); for(int i=1;i<=p;i++){ scanf("%d",&num); for(int j=1;j<=num;j++){ scanf("%d",&a); g[i][a]=true; } } if(p==hungary()){ printf("YES\n"); } else{ printf("NO\n"); } } return 0; }