hdu1083

#include"stdio.h" #include"string.h" #define N 305 int mark[N],link[N],map[N][N],p; int find(int a) //匈牙利算法，二分匹配 { int i; for(i=1;i<=p;i++) { if(!mark[i]&&map[a][i]) { mark[i]=1; if(!link[i]||find(link[i]))//若i已经配对，则查找和i配对的 { //那个元素是否还能和其他元素配对 link[i]=a; return 1; } } } return 0; } int main() { int t,n,i,a,m,ans; scanf("%d",&t); while(t--) { memset(link,0,sizeof(link)); memset(map,0,sizeof(map)); scanf("%d%d",&p,&n); for(i=1;i<=p;i++) { scanf("%d",&m); while(m--) { scanf("%d",&a); map[a][i]=1; } } ans=0; for(i=1;i<=n;i++) { memset(mark,0,sizeof(mark)); ans+=find(i); } if(ans==p) //最大匹配数等于课程数 printf("YES\n"); else printf("NO\n"); } return 0; }