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