题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2255
题意：有N个人跟N个房子,每个人跟房子都有一定的距离,现在要让这N个人全部回到N个房子里面去,要求所有人回去的距离最短.
KM算法模板题~
#include "stdio.h" //hdu 2255
#include "string.h"
#include "stdlib.h" #define N 305
#define INF 0x3fffffff int n;
int match[N];
int map[N][N];
int lx[N],ly[N]; bool s[N],t[N];//s[],t[]记录当前左/右第i个点是否在匈牙利树中 inline int MIN(int a,int b) { return a<b?a:b; }
inline int MAX(int a,int b) { return a>b?a:b; } bool find(int x) //匈牙利,匹配（找增广路）
{
int y;
s[x] = true;
for(y=1; y<=n; ++y)
{
if(!t[y] && lx[x]+ly[y]==map[x][y])
{
t[y] = true;
if(match[y]==-1 || find(match[y]))
{
match[y] = x;
return true;
}
}
}
return false;
} int KM()
{
int i,j,k;
int ans=0;
memset(match,-1,sizeof(match));
memset(lx,0,sizeof(lx));
memset(ly,0,sizeof(ly));
for(i=1; i<=n; ++i) //初始化S顶标为最大权
{
for(j=1; j<=n; ++j)
lx[i] = MAX(lx[i],map[i][j]);
}
for(i=1; i<=n; ++i) //匹配每一个点
{
while(1)
{
memset(s,0,sizeof(s));
memset(t,0,sizeof(t));
if(find(i)) //点i匹配成功
break;
else //匹配失败，找最小值num
{
int num = INF;
for(j=1; j<=n; ++j)
{
if(s[j]) //j在匈牙利树中
{
for(k=1; k<=n; ++k)
{
if(!t[k]) //k在匈牙利树外
num = MIN(num,lx[j]+ly[k]-map[j][k]);
}
}
}
for(k=1; k<=n; ++k) //修改顶标
{
if(s[k]) lx[k] -= num; //保证至少有一条边可以加入
if(t[k]) ly[k] += num; //保证原来匹配的边修改后依然可以匹配
}
}
}
}
for(i=1; i<=n; ++i)
ans += map[match[i]][i];
return ans;
} int main()
{
int i,j;
while(scanf("%d",&n)!=-1)
{
for(i=1; i<=n; ++i)
{
for(j=1; j<=n; ++j)
scanf("%d",&map[i][j]);
}
printf("%d\n",KM());
}
return 0;
}