| ||||||||||
| 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