「HDU-3488」Tour (有向环覆盖问题)

发表于 | 分类于 ，

「HDU-3488」Tour
二分图最大权匹配，有向环覆盖问题

题意

给定一个$n$个顶点、$m$条边的有向图，要求用一个或多个不相交的有向环覆盖所有的节点。问该有向环所有权值的总和最小为多少。

解法

因为路径由一个或多个不相交的有向环组成，对于匹配之后图中的每一点，其入度=出度=1，即拆点后二分图可以满足完备匹配，二分图中的边即为有向环中的边。

由于要求的答案为最小权匹配，初始化时需要将边的权值取负数，建立二分图，调用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
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=200+10;
const int inf=0x3f3f3f3f;

int n;
int lx[maxn],ly[maxn],edge[maxn][maxn];
int match[maxn],delta;
bool vx[maxn],vy[maxn];

bool dfs(int x)	
{
	vx[x]=true;
	for(int y=1;y<=n;y++)
	{
		if(!vy[y])
		{
			int tmp=lx[x]+ly[y]-edge[x][y];
			if(!tmp)	
			{
				vy[y]=true;
				if(!match[y]||dfs(match[y]))
				{
					match[y]=x;
					return true;
				}
			}
			else delta=min(delta,tmp);
		}
	}
	return false;
}

int KM()
{
	for(int i=1;i<=n;i++)	
	{
		lx[i]=-inf;
		ly[i]=0;
		for(int j=1;j<=n;j++)
			lx[i]=max(lx[i],edge[i][j]);
	}
	memset(match,0,sizeof(match));
	for(int x=1;x<=n;x++)
	{
		for(;;)
		{
			delta=inf;
			memset(vx,0,sizeof(vx));
			memset(vy,0,sizeof(vy));
			if(dfs(x)) break;
			for(int i=1;i<=n;i++)	
			{
				if(vx[i]) lx[i]-=delta;
				if(vy[i]) ly[i]+=delta;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
        if(match[i]) ans-=edge[match[i]][i];
    return ans;
}

int main()
{
    int t,m,u,v,w;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(edge,-inf,sizeof edge);
        while(m--)
        {
            scanf("%d%d%d",&u,&v,&w);
            edge[u][v]=max(edge[u][v],-w);
        }
        printf("%d\n",KM());
    }
    return 0;
}