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]; void addedge(int u,int v) { th[cnt].e=v; th[cnt].next=head[u]; head[u]=cnt++; } int gungary(int u) { 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; } } } 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++){ scanf("%d",&u); for(j=0;j<u;j++){ scanf("%d",&v); 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)) 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