// S是未匹配的顶点集
1.
while
(M 不是 Mp)
1.
{
1.
//F(S)是Gf中与S中顶点相邻的顶点集
1.
if
（ F(S)==T ）
1.
{
1.
d = min( f[u]+f[w]-weight[u][w] );
//u in S, w not in T
1.
for
each v in V
1.
{
1.
if
( v in S )
1.
f[v]=f[v]-d;
1.
else
1.
if
( v in T )
1.
f[v]=f[v]-d;
1.
1.
}
1.
}
1.
else
//
1.
{
1.
w = F(S)-T中一个顶点
1.
if
( w未匹配 )
1.
{
1.
P是刚找到的增大路径
1.
M = M与P的对称差分运算结果
1.
S是某个未匹配的顶点
1.
T= null
1.
}
1.
else
1.
{
1.
S=S+ {M中w的相邻点}
1.
T=T+w
1.
}
1.
}
1.
}
最后给一个代码，跟伪代码的思路不是很一样。从网上找的
[cpp] view plain copy
#include <cstdio>
1.
#include <memory.h>
1.
#include <algorithm> // 使用其中的 min 函数
1.
using
namespace
std;
1.
const
int
MAX = 1024;
1.
int
n;
// X 的大小
1.
int
weight [MAX] [MAX];
// X 到 Y 的映射（权重）
1.
int
lx [MAX], ly [MAX];
// 标号
1.
bool
sx [MAX], sy [MAX];
// 是否被搜索过
1.
int
match [MAX];
// Y(i) 与 X(match [i]) 匹配
1.
// 初始化权重
1.
void
init (
int
size);
1.
// 从 X(u) 寻找增广道路，找到则返回 true
1.
bool
path (
int
u);
1.
// 参数 maxsum 为 true ，返回最大权匹配，否则最小权匹配
1.
int
bestmatch (
bool
maxsum =
true
);
1.
void
init (
int
size)
1.
{
1.
// 根据实际情况，添加代码以初始化
1.
n = size;
1.
for
(
int
i = 0; i < n; i ++)
1.
for
(
int
j = 0; j < n; j ++)
1.
scanf (
"%d"
, &weight [i] [j]);
1.
}
1.
1.
bool
path (
int
u)
1.
{
1.
sx [u] =
true
;
1.
for
(
int
v = 0; v < n; v ++)
1.
if
(!sy [v] && lx[u] + ly [v] == weight [u] [v])
1.
{
1.
sy [v] =
true
;
1.
if
(match [v] == -1 || path (match [v]))
1.
{
1.
match [v] = u;
1.
return
true
;
1.
}
1.
}
1.
return
false
;
1.
}
1.
int
bestmatch (
bool
maxsum)
1.
{
1.
int
i, j;
1.
if
(!maxsum)
1.
{
1.
for
(i = 0; i < n; i ++)
1.
for
(j = 0; j < n; j ++)
1.
weight [i] [j] = -weight [i] [j];
1.
}
1.
// 初始化标号
1.
for
(i = 0; i < n; i ++)
1.
{
1.
lx [i] = -0x1FFFFFFF;
1.
ly [i] = 0;
1.
for
(j = 0; j < n; j ++)
1.
if
(lx [i] < weight [i] [j])
1.
lx [i] = weight [i] [j];
1.
}
1.
memset (match, -1,
sizeof
(match));
1.
for
(
int
u = 0; u < n; u ++)
1.
while
(1)
1.
{
1.
memset (sx, 0,
sizeof
(sx));
1.
memset (sy, 0,
sizeof
(sy));
1.
if
(path (u))
1.
break
;
1.
// 修改标号
1.
int
dx = 0x7FFFFFFF;
1.
for
(i = 0; i < n; i ++)
1.
if
(sx [i])
1.
for
(j = 0; j < n; j ++)
1.
if
(!sy [j])
1.
dx = min (lx[i] + ly [j] – weight [i] [j], dx);
1.
for
(i = 0; i < n; i ++)
1.
{
1.
if
(sx [i])
1.
lx [i] -= dx;
1.
if
(sy [i])
1.
ly [i] += dx;
1.
}
1.
}
1.
int
sum = 0;
1.
for
(i = 0; i < n; i ++)
1.
sum += weight [match [i]] [i];
1.
if
(!maxsum)
1.
{
1.
sum = -sum;
1.
for
(i = 0; i < n; i ++)
1.
for
(j = 0; j < n; j ++)
1.
weight [i] [j] = -weight [i] [j];
// 如果需要保持 weight [ ] [ ] 原来的值，这里需要将其还原
1.
}
1.
return
sum;
1.
}
1.
1.
int
main()
1.
{
1.
freopen (
"in.txt"
,
"r"
, stdin);
1.
int
n;
1.
scanf (
"%d"
, &n);
1.
init (n);
1.
int
cost = bestmatch (
true
);
1.
printf (
"%d /n"
, cost);
1.
for
(
int
i = 0; i < n; i ++)
1.
{
1.
printf (
"Y %d -> X %d /n"
, i, match [i]);
1.
}
1.
return
0;
1.
}
1.
/*
1.
5
1.
3 4 6 4 9
1.
6 4 5 3 8
1.
7 5 3 4 2
1.
6 3 2 2 5
1.
8 4 5 4 7
1.
//执行bestmatch (true) ，结果为 29
1.
*/
1.
/*
1.
5
1.
7 6 4 6 1
1.
4 6 5 7 2
1.
3 5 7 6 8
1.
4 7 8 8 5
1.
2 6 5 6 3
1.
//执行 bestmatch (false) ，结果为 21
1.
*/
