km（带权最优匹配）.txt

图论常用算法的C语言程序,对于图论的一些应用有很大的指导作用!

#include <stdio.h>
#include <string.h>
#define N 1001
#define M 1<<30

int n;
int m[N][N]={0};
int link[N]={0};
int lx[N]={0},ly[N]={0};
bool x[N]={0},y[N]={0};

int Min(int a,int b) {return a<b?a:b;}

void init()
{
 int i,j;
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   if(m[i][j]>lx[i]) lx[i]=m[i][j];
 memset(link,-1,sizeof(link));
}

bool Find(int a)         //用匈牙利找最大匹配
{
 int i,d;
 x[a]=true;

 for(i=1;i<=n;i++)
 {
  if(!y[i]&&m[a][i]==lx[a]+ly[i])
  {
   y[i]=true;
   if(link[i]==-1||Find(link[i])) 
   {
    link[i]=a;
    return true;
   }
  }
 }
 return false;
}

void KM()
{
 int i,j,k,d;
 int cost=0;
 init();
 
 for(i=1;i<=n;i++)
 {
  while(1)
  {
   memset(x,0,sizeof(x));
   memset(y,0,sizeof(y));

   if(Find(i)) break;          //若找到最大匹配，结束

   d=M;

   for(j=1;j<=n;j++)
    if(x[j])
	 for(k=1;k<=n;k++)
	  if(!y[k])
	   d=Min(d,lx[j]+ly[k]-m[j][k]);   //找ld+;y中最小值d

   if(d==M) break;

   for(j=1;j<=n;j++)          //修改lx,ly
   {
    if(x[j]) lx[j]-=d;
    if(y[j]) ly[j]+=d;
   }
  }

 }

 for(i=1;i<=n;i++)
 {
  cost+=m[link[i]][i];
 }
 printf("\n%d\n",cost);
}

int main()
{
 int i,j;
 scanf("%d",&n);
 
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   scanf("%d",&m[i][j]);
 
 KM();
 scanf("%d",&i);
}