（转）KM算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[i]，顶点Yi的顶标为B [i]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[i]+B[j]>=w[i,j]始终 成立。KM算法的正确性基于以下定理：
若由二分图中所有满足A[i]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。
这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。
初始时为了使A[i]+B[j]>=w[i,j]恒成立，令A[i]为所有与顶点Xi关联的边的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。
我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现：
两端都在交错树中的边(i,j)，A[i]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。
两端都不在交错树中的边(i,j)，A[i]和B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。
X端不在交错树中，Y端在交错树中的边(i,j)，它的A[i]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。
X端在交错树中，Y端不在交错树中的边(i,j)，它的A[i]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。
现在的问题就是求d值了。为了使A[i]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图，d应该等于min{A[i]+B[j]-w[i,j]|Xi在交错树中，Yi不在交错树中}。
以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶 标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个“松弛量”函数 slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slack[j]变成原值与A [i]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点：修改 顶标后，要把所有的slack值都减去d。
POJ 2195
http://acm.pku.edu.cn/JudgeOnline/problem?id=2195
HDU 1533
http://acm.hdu.edu.cn/showproblem.php?pid=1533
第一道二分图最佳匹配题，简单题，会二分最佳的这题也就会。就建图的时候要把距离算出来！
代码
#include <iostream>
#include <cmath>
using namespace std;
int n,m;
int num1,num2;
char map[150][150]; //初始输入
int mat[150][150]; //记录距离
int house[150][2]; //房子坐标
int man[150][2]; //人的坐标
int pl[150],pr[150]; //左右顶标
int visl[150],visr[150]; //是否被访问
int match[150]; //匹配
int stack[150];
int Min(int a,int b)
{
return a>b?b:a;
}
bool find(int a) // 找增广路径
{
int i;
visl[a] = 1;
for(i=0;i<num2;i++)
{
if(visr[i] == 0)
{
int val = pl[a] + pr[i] - mat[a][i];
if(val == 0)
{
visr[i] = 1;
if(match[i] == -1 || find(match[i]))
{
match[i] = a;
return 1;
}
}
else
{
if(val < stack[i])
stack[i] = val;
}
}
}
return 0;
}
int km()
{
int i,j,k;
//初始化顶标
for(i=0;i<num1;i++)
{
pl[i] = -0x7ffffff;
pr[i] = 0;
for(j=0;j<num2;j++)
{
if(mat[i][j] > pl[i])
pl[i] = mat[i][j];
}
}
memset(match,-1,sizeof(match));
for(k=0;k<num1;k++)
{
for(i=0;i<150;i++)
stack[i] = 0x7fffffff;
while(1)
{
memset(visl,0,sizeof(visl));
memset(visr,0,sizeof(visr));
if(find(k))
break;
int d = 0x7ffffff;
for(j=0;j<num2;j++)
{
if(!visr[j])
d = Min(stack[j] , d);
}
for(i=0;i<num1;i++)
{
if(visl[i])
pl[i] -= d;
if(visr[i])
pr[i] += d;
}
}
}
int sum = 0;
for(i=0;i<num1;i++)
{
sum += -1 * mat[match[i]][i];
}
return sum;
}
void Init()
{
int i,j;
num1 = 0; //房子个数
num2 = 0; //人的个数
for(i=0;i<n;i++)
{
cin>>map[i];
for(j=0;j<m;j++)
{
if(map[i][j] == 'H')
{
house[num1][0] = i;
house[num1++][1] = j;
}
if(map[i][j] == 'm')
{
man[num2][0] = i;
man[num2++][1] = j;
}
}
}
for(i=0;i<num1;i++)
{
for(j=0;j<num2;j++)
{
mat[i][j] = abs(house[i][0] - man[j][0]) + abs(house[i][1] - man[j][1]);
mat[i][j] = - mat[i][j]; //因为是取最小权值，所以取反
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF && (n!=0 || m!=0))
{
Init();
printf("%d\n",km());
}
return 0;
}
HDU 3488
http://acm.hdu.edu.cn/showproblem.php?pid=3488
题目出的比较隐藏，我记得当时我做的时候根本想不到是二分图最佳匹配，如果明白是二分图的话，还是很容易能理解的，就是一个最佳匹配！
需要注意的一点是该题求的是最小值，先吧每条边取反，求最佳匹配，输出的时候再取反回来！
代码
#include <iostream>
using namespace std;
#define min(a,b) (a>b?b:a);
const long maxn = 205;
const long inf = 1000000000;
int n,m; //n：点数 m：边数
int nl,nr;
int pl[maxn],pr[maxn]; //左右顶标
int map[maxn][maxn];
int match[maxn]; //匹配边
int stack[maxn];
bool visl[maxn],visr[maxn];
void Init()
{
int i,j;
int a,b,c;
scanf("%d%d",&n,&m);
nl = nr = n;
for(i=0;i<maxn;i++)
for(j=0;j<maxn;j++)
map[i][j] = inf;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(c < map[a][b])
{
map[a][b] = c;
}
}
for(i=1;i<=nl;i++)
{
for(j=1;j<=nr;j++)
map[i][j] *= -1;
}
}
bool find(int dir)
{
int i,j;
visl[dir] = 1;
for(i=1;i<=nr;i++)
{
if(0 == visr[i])
{
int val = pl[dir] + pr[i] - map[dir][i];
if(0 == val)
{
visr[i] = 1;
if(match[i] == -1 || find(match[i]))
{
match[i] = dir;
return true;
}
}
else
{
if(val < stack[i])
stack[i] = val;
}
}
}
return false;
}
void KM()
{
int i,j,k;
/*初始化顶标*/
for(i=1;i<=nl;i++)
{
pl[i] = -inf;
pr[i] = 0;
for(j=1;j<=nr;j++)
{
if(map[i][j] > pl[i])
pl[i] = map[i][j];
}
}
memset(match,-1,sizeof(match));
for(k=1;k<=nl;k++) //左边的点
{
fill(stack,stack+maxn,inf);
while(1)
{
memset(visl,0,sizeof(visl));
memset(visr,0,sizeof(visr));
if(find(k))
break;
int d = inf;
for(i=1;i<=nr;i++)
{
if(0 == visr[i])
{
d = min(stack[i],d);
}
}
for(i=1;i<=nl;i++)
if(1 == visl[i])
pl[i] -= d;
for(i=1;i<=nr;i++)
if(1 == visr[i])
pr[i] += d;
}
}
}
void Print()
{
int sum = 0;
int i;
for(i=1;i<=nr;i++)
{
if(match[i] != -1)
sum += -1 * map[match[i]][i];
}
printf("%d\n",sum);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
Init();
KM();
Print();
}
return 0;
}
HDU 2448
http://acm.hdu.edu.cn/showproblem.php?pid=2448
最短路径+二分匹配
先求出每条船所在的采矿点跟所有港口的最短距离，然后对这个图进行二分最佳匹配就行！
注意一点：因为船进入港口之后就不会再出来，所以输入时采矿点的港口的距离是单向的
代码
#include <iostream>
using namespace std;
#define min(a,b) (a>b?b:a)
typedef int elem_t;
const long maxn = 310;
const long inf = 1000000000;
int n,m,p,q; //n个港口，m个采矿点
int dir[maxn]; //船一开始停留的位置
int map[maxn][maxn]; //初始图，1 - n 表示港口， n+1 - n+m 表示采矿点
int Min[maxn][maxn]; //各个点的最短记录
int pre[maxn][maxn]; //路径保存，这题没用
int nl,nr;
int pl[maxn],pr[maxn]; //左右顶标
bool visl[maxn],visr[maxn]; //X和Y是否被访问
int mat[maxn][maxn]; //建立起来的二分图
int match[maxn]; //Y中与X的匹配关系
int stack; //最小d值
void Init()
{//原图的输入
int i,j;
int a,b,c;
for(i=1;i<=n;i++)
{
scanf("%d",&dir[i]);
dir[i] += n;
}
for(i=0;i<maxn;i++)
for(j=0;j<maxn;j++)
map[i][j] = inf;
for(i=1;i<=p;i++)
{
scanf("%d%d%d",&a,&b,&c);
{
a += n;
b += n;
if(c < map[a][b])
map[a][b] = map[b][a] = c; //这里是双向的
}
}
for(i=1;i<=q;i++)
{
scanf("%d%d%d",&a,&b,&c);
b += n;
if(c < map[b][a])
map[b][a] = c; //就是这里，应该是单向的
}
}
//floyd求最短距离
void floyd_warshall(int n,elem_t mat[][maxn],elem_t min[][maxn],int pre[][maxn]){
int i,j,k;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
min[i][j]=mat[i][j],pre[i][j]=(i==j)?-1:i;
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (min[i][k]+min[k][j]<min[i][j])
min[i][j]=min[i][k]+min[k][j],pre[i][j]=pre[k][j];
}
void _Init()
{//对二分图的建图
int i,j;
nl = nr = n;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
mat[i][j] = Min[dir[i]][j];
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
mat[i][j] *= -1;
}
}
bool find(int a)
{
int i,j;
visl[a] = 1;
for(i=1;i<=nr;i++)
{
if(0 == visr[i])
{
int val = pl[a] + pr[i] - mat[a][i];
if(0 == val)
{
visr[i] = 1;
if(-1 == match[i] || find(match[i]))
{
match[i] = a;
return true;
}
}
else
{
if(val < stack)
stack = val;
}
}
}
return false;
}
void KM()
{
int i,j;
for(i=1;i<=nl;i++)
{
pl[i] = -1 * inf;;
pr[i] = 0;
for(j=1;j<=nr;j++)
{
if(mat[i][j] > pl[i])
pl[i] = mat[i][j];
}
}
memset(match,-1,sizeof(match));
for(j=1;j<=nl;j++)
{
stack = inf;
while(1)
{
memset(visl,0,sizeof(visl));
memset(visr,0,sizeof(visr));
if(find(j))
break;
int d = stack;
for(i=1;i<=nl;i++)
if(1 == visl[i])
pl[i] -= d;
for(i=1;i<=nr;i++)
if(1 == visr[i])
pr[i] += d;
}
}
}
void Print()
{
int i;
int sum = 0;
for(i=1;i<=nr;i++)
{
if(match[i] != -1)
sum += -1 * mat[match[i]][i];
}
printf("%d\n",sum);
}
int main()
{
while(scanf("%d%d%d%d",&n,&m,&p,&q)!=EOF)
{
Init();
floyd_warshall(n+m,map,Min,pre);
_Init();
KM();
Print();
}
return 0;
}
HDU 3722
http://acm.hdu.edu.cn/showproblem.php?pid=3722
简单二分最佳匹配
HDU 2426
http://acm.hdu.edu.cn/showproblem.php?pid=2426
也是一道简答的二分匹配题，初始化时把为负值的不要输入就行！
但这题数据量大了一点，我如果用Lost的那个模板，用stack而不用stack数组拿来优化的话就会超时！
代码
#include <iostream>
using namespace std;
#define min(a,b) (a>b?b:a)
const long maxn = 505;
const long inf = 1000000000;
int cas = 0;
int E;
int nl,nr;
int pl[maxn],pr[maxn]; //左右顶标
bool visl[maxn],visr[maxn]; //X和Y是否被访问
int mat[maxn][maxn]; //建立起来的二分图
int match[maxn]; //Y中与X的匹配关系
int stack[maxn]; //最小d值
void Init()
{
int i,j;
int a,b,c;
for(i=0;i<maxn;i++)
for(j=0;j<maxn;j++)
mat[i][j] = -inf;
for(i=0;i<E;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(c >= 0)
{
a += 1;
b += 1;
mat[a][b] = c;
}
}
}
bool find(int a)
{
int i,j;
visl[a] = 1;
for(i=1;i<=nr;i++)
{
if(0 == visr[i])
{
int val = pl[a] + pr[i] - mat[a][i];
if(0 == val)
{
visr[i] = 1;
if(-1 == match[i] || find(match[i]))
{
match[i] = a;
return true;
}
}
else
{
if(val < stack[i])
stack[i] = val;
}
}
}
return false;
}
void KM()
{
if(E == 0)
return;
int i,j;
for(i=1;i<=nl;i++)
{
//pl[i] = -1 * inf;
pl[i] = 0;
for(j=1;j<=nr;j++)
{
if(mat[i][j] > pl[i])
pl[i] = mat[i][j];
}
}
for(i=1;i<=nr;i++)
pr[i] = 0;
memset(match,-1,sizeof(match));
for(j=1;j<=nl;j++)
{
fill(stack,stack+maxn,inf);
while(1)
{
memset(visl,0,sizeof(visl));
memset(visr,0,sizeof(visr));
if(find(j))
break;
int d = inf;
for(i=1;i<=nr;i++)
{
if(visr[i] == 0)
{
d = min(stack[i],d);
}
}
for(i=1;i<=nl;i++)
if(1 == visl[i])
pl[i] -= d;
for(i=1;i<=nr;i++)
{
if(1 == visr[i])
pr[i] += d;
//else
stack[i] -= d;
}
}
}
}
void Print()
{
int i;
int sum = 0;
int sumt = 0;
printf("Case %d: ",++cas);
for(i=1;i<=nr;i++)
{
if(match[i] != -1 && mat[match[i]][i] != -inf)
{
sumt++;
sum += mat[match[i]][i];
}
}
if(sumt < nl)
{
sum = -1;
}
printf("%d\n",sum);
}
int main()
{
while(scanf("%d%d%d",&nl,&nr,&E) != EOF)
{
Init();
if(E == 0)
{
printf("Case %d: ", ++cas);
printf("-1\n");
continue;
}
KM();
Print();
}
}