概述
找了标程研究了一下，修改成自己的风格了，贴上来。
引用：
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。
#include
<
memory.h
>
#include
<
algorithm
>
//
使用其中的 min 函数
using
namespace
std;
const
int
MAX
=
1024
;
int
n;
//
X 的大小
int
weight [MAX] [MAX];
//
X 到 Y 的映射（权重）
int
lx [MAX], ly [MAX];
//
标号
bool
sx [MAX], sy [MAX];
//
是否被搜索过
int
match [MAX];
//
Y(i) 与 X(match [i]) 匹配
//
初始化权重
void
init (
int
size);
//
从 X(u) 寻找增广道路，找到则返回 true
bool
path (
int
u);
//
参数 maxsum 为 true ，返回最大权匹配，否则最小权匹配
int
bestmatch (
bool
maxsum
=
true
);
void
init (
int
size)
{
//
根据实际情况，添加代码以初始化
n
=
size;
for
(
int
i
=
0
; i
<
n; i
++
)
for
(
int
j
=
0
; j
<
n; j
++
)
scanf (
"
%d
"
,
&
weight [i] [j]);
}
bool
path (
int
u)
{
sx [u]
=
true
;
for
(
int
v
=
0
; v
<
n; v
++
)
if
(
!
sy [v]
&&
lx[u]
+
ly [v]
==
weight [u] [v])
{
sy [v]
=
true
;
if
(match [v]
==
-
1
||
path (match [v]))
{
match [v]
=
u;
return
true
;
}
}
return
false
;
}
int
bestmatch (
bool
maxsum)
{
int
i, j;
if
(
!
maxsum)
{
for
(i
=
0
; i
<
n; i
++
)
for
(j
=
0
; j
<
n; j
++
)
weight [i] [j]
=
-
weight [i] [j];
}
//
初始化标号
for
(i
=
0
; i
<
n; i
++
)
{
lx [i]
=
-
0x1FFFFFFF
;
ly [i]
=
0
;
for
(j
=
0
; j
<
n; j
++
)
if
(lx [i]
<
weight [i] [j])
lx [i]
=
weight [i] [j];
}
memset (match,
-
1
,
sizeof
(match));
for
(
int
u
=
0
; u
<
n; u
++
)
while
(
1
)
{
memset (sx,
0
,
sizeof
(sx));
memset (sy,
0
,
sizeof
(sy));
if
(path (u))
break
;
//
修改标号
int
dx
=
0x7FFFFFFF
;
for
(i
=
0
; i
<
n; i
++
)
if
(sx [i])
for
(j
=
0
; j
<
n; j
++
)
if
(
!
sy [j])
dx
=
min (lx[i]
+
ly [j]
-
weight [i] [j], dx);
for
(i
=
0
; i
<
n; i
++
)
{
if
(sx [i])
lx [i]
-=
dx;
if
(sy [i])
ly [i]
+=
dx;
}
}
int
sum
=
0
;
for
(i
=
0
; i
<
n; i
++
)
sum
+=
weight [match [i]] [i];
if
(
!
maxsum)
{
sum
=
-
sum;
for
(i
=
0
; i
<
n; i
++
)
for
(j
=
0
; j
<
n; j
++
)
weight [i] [j]
=
-
weight [i] [j];
// 如果需要保持 weight [ ] [ ] 原来的值，这里需要将其还原
}
return sum;
}
int main()
{
int n;
scanf ("%d", &n);
init (n);
int cost = bestmatch (true);
printf ("%d ", cost);
for (int i = 0; i < n; i ++)
{
printf ("Y %d -> X %d ", i, match [i]);
}
return 0;
}
/*
5
3 4 6 4 9
6 4 5 3 8
7 5 3 4 2
6 3 2 2 5
8 4 5 4 7
//执行bestmatch (true) ，结果为 29
*/
/*
5
7 6 4 6 1
4 6 5 7 2
3 5 7 6 8
4 7 8 8 5
2 6 5 6 3
//执行 bestmatch (false) ，结果为 21
*/
这个实现和图论书上描述的有所不同，这个和匈牙利算法方法上是一样的（不断地寻找增广道路。。），而不是像书上在过程中调用匈牙利算法。。
最后
以上就是称心火车为你收集整理的二分图的最佳匹配（KM 算法）的全部内容，希望文章能够帮你解决二分图的最佳匹配（KM 算法）所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复