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 |
邻接矩阵的写法#include<stdio.h> #include<stdlib.h> #include<string.h> /*struct edge{ int e; int next; }th[110*310];*/ int cnt; int head[410],link[410],vis[410],ch[410][410]; /*void addedge(int u,int v) { th[cnt].e=v; th[cnt].next=head[u]; head[u]=cnt++; }*/ int gungary(int u,int m) { int i; /* for(i=head[u];i!=-1;i=th[i].next){ int v=th[i].e; if(!vis[v]){ vis[v]=1; if(link[v]==-1||gungary(link[v])){ link[v]=u; return 1; } } }*/ for(i=0;i<m;i++){ if(ch[u][i]==1&&vis[i]==0){ vis[i]=1; if(link[i]==-1||gungary(link[i],m)){ link[i]=u; return 1; } } } return 0; } int main() { int i,j; int num; int n,m,v,u; scanf("%d",&num); while(num--){ memset(head,-1,sizeof(head)); cnt=0; scanf("%d%d",&n,&m); for(i=0;i<n;i++){ for(j=0;j<m;j++){ ch[i][j]=0; } } for(i=0;i<n;i++){ scanf("%d",&u); for(j=0;j<u;j++){ scanf("%d",&v); ch[i][v-1]=1; /* addedge(i,v-1);*/ } } int ans=0; memset(link,-1,sizeof(link)); for(i=0;i<n;i++){ memset(vis,0,sizeof(vis)); if(gungary(i,m)) ans++; } if(ans!=n) printf("NO\n"); else if(ans==n)printf("YES\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