首先相对于上个blog讲的匈牙利算法用于解决无权二分图的最佳匹配,km算法则是在匈牙利算法基础上更进一层的,每条边增加了权值后,真的开始看时有些无厘头,觉得没有什么好方法,但两位牛人Kuhn-Munkras在1957年提出的，而匈牙利算法是在1965年提出的,
终于翻了图书馆3本书的讲解和无数网上牛人的讲解,终于看懂的,这当然是后话.
首先km算法是在匈牙利算法基础上运行的,本质上km算法大致意思就是先将x集合中每条边连接上其所能连接的最大权值边,如果没有冲突,当然是正确的,有的话,也别急,现在我们要做的是将这个ans逐渐缩小,然后将冲突的边调开,直到满足二分图完备匹配(这个地方用匈牙利算法求最大匹配,若最大匹配是完备匹配,就满足)的时候,此时便是正确的答案.
至于如何将冲突的边进行调整,才能使ans缩小得刚好,又能够使得x集合能够找到各自的y取得最大权值,因此我们给每个x,y集合上的点引入一个可行顶标lx[],ly[],当初就是不明白为什么需要引入这两个顶标才搞了很久,顾名思义,可行顶标就是用来判断当前点是否可行,km算法中即根据lx[i]+ly[j]的大小判断是否I,j能够连接.
可能我们先来证明一个定理会更容易理解km算法:
w[I,j]表示i到j的权值,设W=(wij)(i∈x,j∈y),其中排列{jk1,jk2…,jkn},使最大匹配M=(wij)(其中(in,jkn)连接) ,存在{lx[i]},{ly[j]},满足lx[i]+ly[j]>=w[I,j],且其中lx[in]+ly[jkn]=w[In,jn], 最佳匹配的权值和max(sigma(wij))=min(sigma(lx[])+sigma(ly[]))
举个例子好理解:
|
wij |
j1 |
j2 |
j3 |
|
i1 |
3 |
2 |
* |
|
i2 |
2 |
* |
1 |
|
i3 |
* |
1 |
2 |
一开始我们令所有x集合lx[i]=max(w[i,j]),ly[j]=0,则保证lx[i]+ly[j]>=w[i,j],然后我们通过一个表格来表示x和y之间的关系,
则lx[1]=3lx[2]=2 lx[3]=2 ly[]=0
然后做一个表格表示lx[i]+ly[j]-w[i,j]
|
lx[i]-ly[j]-w[i,j] |
j1 |
j2 |
j3 |
|
i1 |
0 |
1 |
* |
|
i2 |
0 |
* |
1 |
|
i3 |
* |
1 |
0 |
因为要保证lx[i]+ly[j]>=w[i,j]所以我们只匹配lx[i]+ly[j]=w[i,j]的边,即其他lx[i]+ly[j]>w[i,j]的边先去除.
说明:仔细想想,当前这个情况若满足每个0都在不同行不同列,是不是当前这个情况就是最佳匹配,因为现在每个x都选到了最大的y,显然没有比这个更大的匹配了,不过情况比这个复杂些,其中i1,i2都和j1匹配,产生冲突,所以我们应该修正.
是不是有点感觉了,仔细想想,现在我们应该增大0的个数使得存在不同行不同列的0有n个,因为0即表示可以匹配,所以是不是感觉到可以使用匈牙利算法来找出不同行不同列0的个数,只要等于n即表示当前这个ans=max(sigma(wij))是最优的.
不过当前情况不符合匹配,所以我们要适当缩小ans,使得ans缩小到下一个状态,在这个状态中至少要多出一个0,而且其他边的lx[],ly[]不要影响这些的状态,
因此要得到至少多出一个0,我们得将表格中最小的正整数min=(1,1,1)=1减掉,
现在我们是到i2时发现冲突,因此我们得调整lx,ly,然后重新用匈牙利算法匹配,
{入交错图指入队 如上述第一步中i1,i2入了交错图形成i1-j1-i2,现在将入交错图的x点集合为sx,入交错图的y点集合为sy}
这样我们也就是要将i1或者i2与其他的j匹配,所以我们将sx上的点即i1,i2的lx[]下调1,然后将sy的点即j1的ly[]上调1,
这样的话我们得到
lx[1]=2lx[2]=1 lx[3]=2 ly[1]=1 ly[2]=0 ly[3]=0
|
lx[i]-ly[j]-w[i,j] |
j1 |
j2 |
j3 |
|
i1 |
0 |
0 |
* |
|
i2 |
0 |
* |
1 |
|
i3 |
* |
1 |
0 |
多出一个0,现在匈牙利算法计算时就满足完备匹配了ok
我搞的这个数据不太好,一步到位…,不过足以说明了
然后说明一下为什么这样调保证即使还得继续调整也是正确:每次有匹配冲突时,表示x集合上有一点p无法再插入sx中,我们暂时把它当做入了sx,我们得为他或者其他入交错图的x找到一个匹配,p才能真正入sx. 但是原来的0(原来的边)不能被删除,故我们将sy中的点ly+min这样就保证原来的lx+ly=w,原来的边依旧可以用
其中因为|sx|=|sy|+1;sigma(lx[])+sigma(ly[])比之前减少了min*(|sx|-|sy|)=min
也就是:
对于sx,sy上点:lx-min+ly+min=lx+ly不变
对于sx,非sy上点:lx-min+ly<lx+ly缩小也就使得边多出来
对于非sx,sy上点:lx+ly+min>lx+ly又lx+ly>=w,故lx+ly+min依旧满足>=w
对于非sx,非sy上点:无影响
将{sx}上点lx[i]均-min不是就使得在{sx}与{非sy}之间至少出现一条使得lx[i]+ly[j]=w[i,j],即多出至少一条边,从上述表格形式即多出一个0,而且我们是将下一个多出0的情况找到,故这满足最佳匹配.
因此只要经过有限次的重复上述步骤可达到求得min(sigma(lx[])+sigma(ly[]))
即ans
补上代码:
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
int lx[200],ly[200],w[200][200],pre[200];
int n,ans,mi;
bool sx[200],sy[200];
bool path(int p){
sx[p]=1;
int i;
for(i=1;i<=n;i++)
if (!sy[i]&&lx[p]+ly[i]==w[p][i]){
sy[i]=1;//此处要记得将i入sy,否则之后path会挂的...找了很久...
if (pre[i]==0||path(pre[i])){
pre[i]=p;
return 1;
}
}
return 0;
}
int main()
{
int i,j,k;
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
scanf("%d",&w[i][j]);
w[i][j]=w[i][j];
if (w[i][j]>lx[i]) lx[i]=w[i][j];
}
for(i=1;i<=n;i++){
memset(sx,0,sizeof(sx));
memset(sy,0,sizeof(sy));
while (!path(i)){
mi=2000000000;
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
if (sx[j]&&!sy[k]){
if (lx[j]+ly[k]-w[j][k]<mi) mi=lx[j]+ly[k]-w[j][k];
}
for(j=1;j<=n;j++) if(sx[j]) lx[j]-=mi;
for(j=1;j<=n;j++) if(sy[j]) ly[j]+=mi;
memset(sx,0,sizeof(sx));
memset(sy,0,sizeof(sy));
}
}
for(i=1;i<=n;i++)
ans+=lx[i]+ly[i];
printf("%d",ans);
return 0;
}