匈牙利（二分图最大匹配）.txt

来自「图论常用算法的C语言程序,对于图论的一些应用有很大的指导作用!」· 文本 代码 · 共 50 行

#include <stdio.h>
#include <string.h>
#define N 101

struct points
{
 int road[N];
 int num;
 int pla;
}point[N]={0};

int n,m;
int res[N]={0};
bool check[N]={0};

bool sea(int a)
{
 int i,mid;
 for(i=point[a].pla;i<point[a].num;i++)
 {
  mid=point[a].road[i];
  if(check[mid]) continue;
  if(res[mid]==-1||sea(res[mid]))
  {res[mid]=a;point[a].pla=i+1;check[mid]=true;return true;}
 }
 point[a].pla=point[a].num;
 return false;
}

int main()
{
 int k,a,b,i,j,ans;
 scanf("%d %d %d",&n,&m,&k);
 while(k--)
 {
  scanf("%d %d",&a,&b);
  point[a].road[point[a].num++]=b;
 }
 
 for(i=1;i<=n+m;i++) res[i]=-1;
 
 for(i=1;i<=n;i++)
 {
  for(j=1;j<=n+m;j++) {/*point[j].pla=0;*/check[j]=0;}
  sea(i);
 }
 printf("\n%d\n",ans);
 scanf("%d",&i);
}