求救：有谁知道二分图的匹配算法

半透明的脸

哪位高手会用匈牙利算法求二分图的最大匹配用c语言实现?

wxp19831104

二分图的最大匹配不是用最大网络流的算法吗？

ArXoR

去看看图论的书吧,知道原理了就容易实现了
最大流可以做,但不是最好

xiehui169_1982

#include<stdio.h>
#include<string.h>
main()
{
bool map[100][300];
int i,i1,i2,num,num1,que[300],cou,stu,match1[100],match2[300],pque,p1,now,prev[300],n;
scanf("%d",&n);
for(i=0;i<n;i++)
{
  scanf("%d%d",&cou,&stu);
  memset(map,0,sizeof(map));
  for(i1=0;i1<cou;i1++)
  {
   scanf("%d",&num);
   for(i2=0;i2<num;i2++)
   {
    scanf("%d",&num1);
    map[i1][num1-1]=true;
   }
  }
  num=0;
  memset(match1,int(-1),sizeof(match1));
  memset(match2,int(-1),sizeof(match2));
  for(i1=0;i1<cou;i1++)
  {
   p1=0;
   pque=0;
   for(i2=0;i2<stu;i2++)
   {
    if(map[i1][i2])
    {
     prev[i2]=-1;
     que[pque++]=i2;
    }
    else
     prev[i2]=-2;
   }
   while(p1<pque)
   {
    now=que[p1];
    if(match2[now]==-1)
     break;
    p1++;
    for(i2=0;i2<stu;i2++)
    {
     if(prev[i2]==-2&&map[match2[now]][i2])
     {
      prev[i2]=now;
      que[pque++]=i2;
     }
    }
   }
   if(p1==pque)
    continue;
   while(prev[now]>=0)
   {
    match1[match2[prev[now]]]=now;
    match2[now]=match2[prev[now]];
    now=prev[now];
   }
   match2[now]=i1;
   match1[i1]=now;
   num++;
  }
  if(num==cou)
   printf("YES\n");
  else
   printf("NO\n");
}
}