最小树形图

最小树形图

定义

有向图中固定根的最小“生成树”,即根可以通过树边到达图中任意一个点,且所有树边的权值和最小。

算法思想

设最终得到的最小树形图为 $T$,原图为 $G$。

考虑将每个点权值最小的入边加入 $T$ 中。若 $T$ 中无环,则 $T$ 就是图 $G$ 的最小树形图。

为什么不是出边呢?因为在最终的树形图中每个点的入度都为1,但出度不一定为1。

这样做的正确性?因为图 $G$ 中所有的点都存在于 $T$ 中,因此对于任意一点 $u$,它可以选择任意一条入边加入 $T$ 中。所以必然选择权值最小的边。

若 $T$ 中有环,则要考虑从环上去掉一条边。具体去哪条边我们是不知道的,因此我们需要将环缩点之后重新做一次操作。

我们可以发现环中红色的边是要去掉的。

所以我们只要不断重复此过程,直到所得到图无环,我们就得到了最小树形图。

因此时间复杂度为 $O(VE)$

代码

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
const int maxn = 1e3 + 5;
const int INF = 0x3f3f3f3f;
struct Edge {
int u, v, w;
};
struct MDST {
vector<Edge> edges;
int vis[maxn], id[maxn];
int pre[maxn], val[maxn];

void init() { edges.clear(); }
void addEdge(int u, int v, int w) { edges.push_back({u, v, w}); }
int zhuliu(int n, int rt) {
int ans = 0;
for (;;) {
for (int i = 1; i <= n; i++) val[i] = INF, vis[i] = id[i] = 0;
val[rt] = 0;
for (auto &e : edges)
if (e.u != e.v && e.w < val[e.v]) pre[e.v] = e.u, val[e.v] = e.w;
for (int i = 1; i <= n; i++)
if (i != rt && val[i] == INF) return -1;
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (i == rt) continue;
ans += val[i];
int u = i;
// 找环
while (vis[u] != i && !id[u] && u != rt) {
vis[u] = i;
u = pre[u];
}
if (!id[u] && u != rt) {
id[u] = ++cnt;
for (int v = pre[u]; v != u; v = pre[v]) id[v] = cnt;
}
}
if (!cnt) break;
// 重标号缩点
for (int i = 1; i <= n; i++)
if (!id[i]) id[i] = ++cnt;
for (auto &e : edges) {
if (id[e.u] != id[e.v]) e.w -= val[e.v];
e.u = id[e.u], e.v = id[e.v];
}
rt = id[rt];
n = cnt;
}
return ans;
}
};

输出方案

考虑每次缩环之后要记录“新边”和“要被去掉的边”。

新边就是减去权值后新编号的边。

要被去掉的边就是之前权值最小的入边。

因为可能存在某条边被去掉,然后在这之后又被重新使用,如下图。

因此我们要按照逆拓扑序来找。

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
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
struct Edge {
int u, v, w, id;
};
struct MDST {
vector<Edge> edges;
int vis[maxn], id[maxn];
int pre[maxn], val[maxn];
int eid[maxn], used[maxn * 10];
int dele[maxn * 10], add[maxn * 10];
// 10 倍可能不够?

void init() { edges.clear(); }
void addEdge(int u, int v, int w, int id) { edges.push_back({u, v, w, id}); }
int zhuliu(int n, int rt) {
int m = edges.size();
int ans = 0, tot = m;
memset(used, 0, sizeof(used));
for (;;) {
for (int i = 1; i <= n; i++) val[i] = INF, vis[i] = id[i] = 0;
val[rt] = 0;
for (auto &e : edges)
if (e.u != e.v && e.w < val[e.v])
pre[e.v] = e.u, val[e.v] = e.w, eid[e.v] = e.id;
for (int i = 1; i <= n; i++)
if (i != rt && val[i] == INF) return -1;
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (i == rt) continue;
used[eid[i]]++;
ans += val[i];
int u = i;
while (vis[u] != i && !id[u] && u != rt) {
vis[u] = i;
u = pre[u];
}
if (!id[u] && u != rt) {
id[u] = ++cnt;
for (int v = pre[u]; v != u; v = pre[v]) id[v] = cnt;
}
}
if (!cnt) break;
for (int i = 1; i <= n; i++)
if (!id[i]) id[i] = ++cnt;
for (auto &e : edges) {
if (id[e.u] != id[e.v]) {
e.w -= val[e.v];
dele[tot] = eid[e.v];
add[tot] = e.id;
e.id = tot++;
}
e.u = id[e.u], e.v = id[e.v];
}
rt = id[rt];
n = cnt;
}
for (int i = tot - 1; i >= m; i--) {
if (used[i]) {
used[dele[i]]--;
used[add[i]]++;
}
}
return ans;
}
} mdst;

不定根最小树形图

我们可以通过建立一个虚拟根节点来解决这个问题,虚根向所有点建一条权值为 $val$ 的边。如果得到的结果比两倍的 $val$ 还大,说明图不连通。

$val$ 可以设置为所有边的权值和加一。

那么怎么知道最后选择哪个根呢?因为虚根是不会存在于一个环中,因此从虚根出发的边不会被替换,因此可以记录边的编号。

例题 hdu2121

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 5;
const ll INF = 1e18;
int root;
ll sum;

struct Edge {
int u, v, id;
ll w;
};
struct MDST {
vector<Edge> edges;
int vis[maxn], id[maxn];
int pre[maxn], eid[maxn];
ll val[maxn];
void addEdge(int u, int v, ll w, int id) { edges.push_back({u, v, id, w}); }
ll zhuliu(int n, int rt) {
ll ans = 0;
for (;;) {
for (int i = 1; i <= n; i++) val[i] = INF, vis[i] = id[i] = 0;
val[rt] = 0;
for (auto &e : edges)
if (e.u != e.v && e.w < val[e.v])
pre[e.v] = e.u, val[e.v] = e.w, eid[e.v] = e.id;
for (int i = 1; i <= n; i++)
if (i != rt && val[i] == INF) return -1;
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (i == rt) continue;
if (pre[i] == rt) root = eid[i];
ans += val[i];
if (ans >= 2 * sum) return -1;
int u = i;
while (vis[u] != i && !id[u] && u != rt) {
vis[u] = i;
u = pre[u];
}
if (!id[u] && u != rt) {
id[u] = ++cnt;
for (int v = pre[u]; v != u; v = pre[v]) id[v] = cnt;
}
}
if (!cnt) break;
for (int i = 1; i <= n; i++)
if (!id[i]) id[i] = ++cnt;
for (auto &e : edges) {
if (id[e.u] != id[e.v]) e.w -= val[e.v];
e.u = id[e.u], e.v = id[e.v];
}
rt = id[rt];
n = cnt;
}
return ans;
}
} mdst;
int main() {
int n, m;
while (~scanf("%d%d", &n, &m)) {
mdst.edges.clear();
ll w;
sum = 1;
for (int i = 0, u, v; i < m; i++) {
scanf("%d%d%lld", &u, &v, &w);
++u, ++v;
sum += w;
mdst.addEdge(u, v, w, 0);
}
for (int i = 1; i <= n; i++) mdst.addEdge(n + 1, i, sum, i);
ll ans = mdst.zhuliu(n + 1, n + 1);
if (ans == -1)
puts("impossible");
else
printf("%lld %d\n", ans - sum, root - 1);
puts("");
}
}