hdu 3488 Tour

本文从WordPress迁移而来, 查看全部WordPress迁移文章

二分图 最小权值匹配

题意:给一个有向图,选出一些环,把图中的点都覆盖掉。每个点只能属于一个环即只能被使用一次。每条边都有权值,使得所有边的权值和最小

这题要转化为二分图模型是有些难度的,鉴于题意,可以发现一个事实就是,有n个点的图最终一定用n条边,无论是用了一个环还是多个环。并且是有向边,那么可以看做每个点,引出一条边。将所有顶点看做二分图的X部,虚化出另外一个Y部,对于原图中的边u->v,在二分图中加边u->v’,这样得到的二分图模型,在上面求一次完备匹配,就一定能满足题目说的条件,用一个或多个环覆盖所有顶点(文字难以表达,画图或思考下不难理解)。

另外题目要求权值和最小,那就是求权值和最小的完备匹配,用KM算法即可

KM求最小权值匹配,可以将权值取反,求最大,然后输出的时候再取反,但是也可以写成一个真正意义上的求最小,只需要对应修改求最大的一些语句即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 210
#define INF 1000000
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,X,Y,slack,w[N][N];
int match[N],lx[N],ly[N],xmatch[N],ymatch[N];
bool visx[N],visy[N];

bool findpath(int x){
visx[x] = true;
for(int y = 1; y <= Y; y++){
if(visy[y]) continue;
int temp = w[x][y] - lx[x] - ly[y];
if(temp == 0){
visy[y] = true;
if(ymatch[y] == 0 || findpath(ymatch[y])){
xmatch[x] = y;
ymatch[y] = x;
return true;
}
}
else if(temp < slack) slack = temp;
}
return false;
}

int KM(){
X = Y = n;
cl(ly,0); cl(ymatch,0);
for(int x = 1; x <= X; x++){
lx[x] = INF;
for(int y = 1; y <= Y; y++)
if(w[x][y] != INF && lx[x] > w[x][y])
lx[x] = w[x][y];
}
for(int x = 1; x <= X; x++){
while(true){
cl(visx,false); cl(visy,false);
slack = INF;
if(findpath(x)) break;
for(int x = 1; x <= X; x++)
if(visx[x]) lx[x] += slack;
for(int y = 1; y <= Y; y++)
if(visy[y]) ly[y] -= slack;
}
}
int ans = 0;
for(int x = 1; x <= X; x++)
ans += w[x][xmatch[x]];
return ans;
}

int main(){
int T,m;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
w[i][j] = INF;
while(m--){
int u,v,weight;
scanf("%d%d%d",&u,&v,&weight);
w[u][v] = min(w[u][v],weight);
}
int ans = KM();
printf("%d\n",ans);
}
return 0;
}