计算 二分图带权最大匹配的2种方法: 费用流 / KM
KM算法学习
使用局限性:只能在带权最大匹配是完备匹配的图中使用
完备匹配: G=<V1,V2,E>为二分图,
∣
V
1
∣
<
∣
V
2
∣
|V_1| < |V_2|
∣V1∣<∣V2∣,
M
M
M为
G
G
G中的一个最大匹配数,且
∣
M
∣
=
∣
V
1
∣
|M|= |V_1|
∣M∣=∣V1∣,则称
M
M
M为
V
1
V_1
V1到
V
2
V_2
V2的完备匹配完美匹配:当
∣
V
1
∣
=
∣
V
2
∣
|V_1| = |V_2|
∣V1∣=∣V2∣,若
∣
V
1
∣
<
∣
V
2
∣
|V_1|<|V_2|
∣V1∣<∣V2∣,则完备匹配为
G
G
G中的最大匹配
KM算法准备条件
顶标(顶点标记值),给定第
i
(
1
<
=
i
<
=
N
)
i (1<=i<=N)
i(1<=i<=N)个 左部节点一个整数值
A
i
A_i
Ai,给定第
j
(
1
<
=
j
<
=
N
)
j (1<=j<=N)
j(1<=j<=N)个右部节点一个整数值
B
j
B_j
Bj, 必须满足
∀
i
,
j
,
A
i
+
B
j
≥
w
(
i
,
j
)
\forall i,j, A_i+B_j \geq w(i,j)
∀i,j,Ai+Bj≥w(i,j),
w
(
i
,
j
)
w(i,j)
w(i,j)表示i,j之间的边权( 无 边 设 为 负 无 穷 )
相等子图,二分图中 所有满足
A
i
+
B
j
=
w
(
i
,
j
)
A_i+B_j = w(i,j)
Ai+Bj=w(i,j)的边构成的子图
若相等子图有完备匹配,那么就是带权最大匹配
交错树.左部分的点匹配不成功时dfs访问过的点和边组成的树
KM算法流程
初始化
A
i
=
m
a
x
1
≤
j
≤
N
{
w
(
i
,
j
)
}
A_i = max_{1\leq j \leq N}\{w(i,j)\}
Ai=max1≤j≤N{w(i,j)}(点的所有出边的中的边的值)，
B
j
=
0
B_j=0
Bj=0
dfs过程中记录
K
=
m
i
n
{
A
i
+
B
j
−
w
(
i
,
j
)
}
K = min\{A_i+B_j-w(i,j)\}
K=min{Ai+Bj−w(i,j)}，如果把交错树中左部顶点的顶标全都减小K,右部顶点的顶标增加K:
两端都在交错树的边
(
i
,
j
)
(i,j)
(i,j) ，
A
i
+
B
j
A_i+B_j
Ai+Bj没有变化,仍然属于原来相等子图两端都不在交错树的边
(
i
,
j
)
(i,j)
(i,j)，
A
i
+
B
j
A_i+B_j
Ai+Bj都没变化,仍然不属于原来相等子图左端不在右端在交错树的边
(
i
,
j
)
(i,j)
(i,j)，
A
i
+
B
j
A_i+B_j
Ai+Bj变大,原来不属于,现在更不可能属于左端在而右端不在交错树的边
(
i
,
j
)
(i,j)
(i,j)，
A
i
+
B
j
A_i+B_j
Ai+Bj变小,原来不在,现在可能进入相等子图中,使得相等子图变大,
未找到该点的完备匹配通过上一步修改顶标值一直找下去
例题POJ 2195
要求的是最小权值的完美匹配,将权值转成负值使用KM算法得到最大权值和换成正数也就是最小
#include
<iostream
>
#include
<cstring
>
#include
<vector
>
#include
<cmath
>
#include
<algorithm
>
#include
<stdio
.h
>
#include
<utility
>
using namespace std
;
const int maxn
= 110;
const int
N = 1e4;
int w
[maxn
][maxn
],la
[maxn
],lb
[maxn
],match
[maxn
];
bool va
[maxn
],vb
[maxn
];
int n
,delta
,m
,cnt
;
int house_size
,man_size
;
struct node
{
int x
,y
;
}house
[N],man
[N];
int
distance1(node a
,node b
) {
return abs(a
.x
- b
.x
) + abs(a
.y
- b
.y
);
}
int
dfs(int x
) {
va
[x
] = 1;
for (int y
=1; y
<=house_size
; ++y
) {
if (!vb
[y
])
if (la
[x
] + lb
[y
] - w
[x
][y
] == 0) {
vb
[y
] = 1;
if (!match
[y
] || dfs(match
[y
])) {
match
[y
] = x
;
return 1;
}
}
else delta
= min(delta
,la
[x
]+lb
[y
]-w
[x
][y
]);
}
return 0;
}
int
KM() {
for (int i
=1; i
<=man_size
; ++i
)
for (int j
=1; j
<=house_size
; ++j
)
la
[i
] = max(la
[i
],w
[i
][j
]);
for (int i
=1; i
<=man_size
; ++i
)
while (1) {
memset(va
,0,sizeof va
);
memset(vb
,0,sizeof vb
);
delta
= 1 << 30;
if (dfs(i
)) break;
for (int i
=1; i
<=man_size
; ++i
) {
if (va
[i
]) la
[i
] -= delta
;
if (vb
[i
]) lb
[i
] += delta
;
}
}
int ans
= 0;
for (int i
=1; i
<=house_size
; ++i
) ans
+= w
[match
[i
]][i
];
return ans
;
}
void init() {
house_size
= man_size
=0;
delta
= 0x3f3f3f3f;
memset(w
,0,sizeof w
);
memset(lb
,0,sizeof lb
);
memset(match
,0,sizeof match
);
for (int i
=1; i
<=maxn
; ++i
)
la
[i
] = -0x3f3f3f3f;
}
void read() {
for (int i
=1; i
<=cnt
; ++i
) {
for (int j
=1; j
<=m
; ++j
) {
char ch
= getchar();
if (ch
== 'H') {
house
[house_size
].x
=i
;
house
[house_size
++].y
=j
;
}
else if (ch
== 'm') {
man
[man_size
].x
= i
;
man
[man_size
++].y
=j
;
}
}
getchar();
}
for (int i
=0; i
<man_size
; ++i
)
for (int j
=0; j
<house_size
; ++j
)
w
[i
+1][j
+1] = -distance1(man
[i
],house
[j
]);
}
int
main() {
freopen("1.in","r",stdin
);
while (scanf("%d %d\n",&cnt
,&m
) && cnt
&& m
) {
init();
read();
cout
<< -KM() << endl
;
}
return 0;
}
