Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我擦!还是最大匹配的问题!废话不多说ac了再说!#include<stdio.h> #include <string.h> int n,m,num,temp,i,j,sum; int re[400][400],link[400]; int tag[400]; int DFS(int a) { int ii; for(ii=1;ii<=m;ii++) { if(re[a][ii]!=0&&tag[ii]==0) { tag[ii]=1; if(link[ii]==-1||DFS(link[ii])) { link[ii]=a; return 1; } } } return 0; } int main() { int ca; scanf("%d", &ca); while(ca--) { scanf("%d%d", &n, &m); sum=0; memset(re,0,sizeof(re)); memset(link,-1,sizeof(link)); for(i=1;i<=n;i++) { scanf("%d", &num); for(j=1;j<=num;j++) { scanf("%d", &temp); re[i][temp]=1; } } for(i=1;i<=n;i++) { memset(tag,0,sizeof(tag)); if(DFS(i)==1) sum++; } if(sum==n) printf("YES\n"); else printf("NO\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator