Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5414 Accepted Submission(s): 2600
#include"cstdio" #include"cstring" #include"vector" using namespace std; const int MAXN=300; int P,N; vector<int> G[MAXN*2+10]; int match[MAXN*2+10]; int vis[MAXN*2+10]; void add_edge(int u,int v) { G[u].push_back(v); G[v].push_back(u); } bool dfs(int u) { vis[u]=1; for(int i=0;i<G[u].size();i++) { int v=G[u][i],w=match[v]; if(w<0||(!vis[w]&&dfs(w))) { match[u]=v; match[v]=u; return true; } } return false; } int bipartite_matching() { memset(match,-1,sizeof(match)); int ans=0; for(int i=1;i<=P;i++) { if(match[i]<0) { memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; } } return ans; } int main() { int T; scanf("%d",&T); while(T--) { for(int i=0;i<MAXN*2+10;i++) G[i].clear(); scanf("%d%d",&P,&N); for(int i=1;i<=P;i++) { int s; scanf("%d",&s); while(s--) { int v; scanf("%d",&v); add_edge(i,v+MAXN); add_edge(v+MAXN,i); } } int ans=bipartite_matching(); if(ans==P) printf("YES\n"); else printf("NO\n"); } return 0; }
原文：http://www.cnblogs.com/program-ccc/p/5180666.html