最小樹形圖
在一張有向圖中，如果存在一點 root，滿足：
- 從 root 可以到圖上其他節點。
- root 的入度為 0，其他節點入度為 1。
該圖稱為樹形圖。
在一張圖裡，邊權重和最小的子圖稱為最小樹形圖，也可以說是有向圖版的最小生成樹。
演算法步驟如下：
- 除了 root 之外的所有點選擇權重最小的入邊，如果有點沒有入邊，代表無法形成樹形圖。
- 判斷被選進的邊中有沒有環，如果有環將該還縮成一個點，
- 如果沒出現環終止演算法，否則回到步驟一。
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 | struct Edge
{
int u, v, cost;
};
// in,pre: 每個點最小權重入邊的權重和頂點
// id: 點的新編號, vis: 被誰訪問
vector<int> in(MXN), pre(MXN), id(MXN), vis(MXN);
vector<Edge> E;
int dmst(int root, int n, int m)
{
int res = 0;
while (1)
{
// 尋找非 root 的所有點權重最小的入邊
fill(in.begin(), in.end(), INF);
for (Edge &edge : E)
if (edge.u != edge.v && edge.cost < in[edge.v])
{
in[edge.v] = edge.cost;
pre[edge.v] = edge.u;
}
// 如果有一個點(除了 root)沒入邊，就無法形成樹形圖
for (int i = 0; i < n; ++i)
if (i != root && in[i] == INF)
return -1;
// 找環和縮點
int num = 0;
fill(id.begin(), id.end(), -1);
fill(vis.begin(), vis.end(), -1);
in[root] = 0;
for (int i = 0; i < n; ++i)
{
res += in[i];
int v = i;
while (vis[v] != i && id[v] == -1 && v != root)
{
vis[v] = i;
v = pre[v];
}
if (v != root && id[v] == -1)
{
for (int j = pre[v]; j != v; j = pre[j])
id[j] = num;
id[v] = num++;
}
}
// 沒有環代表已形成樹形圖
if (num == 0)
break;
// 將沒有形成環的點和所有邊重新編號
for (int i = 0; i < n; ++i)
if (id[i] == -1)
id[i] = num++;
for (int i = 0; i < (int)E.size(); ++i)
{
Edge &edge = E[i];
// 假設點 v 有兩條入邊 E1,E2，第一次選擇 E1，在縮點後 E2
// 被選擇，所增加的 cost = E2 的權重 - E1
// 的權重，為了避免重複計算權重，將邊重新編號時把所有未選入的邊權重扣除。
if (id[edge.u] != id[edge.v])
edge.cost -= in[edge.v];
edge.u = id[edge.u];
edge.v = id[edge.v];
}
n = num;
root = id[root];
}
return res;
}
|
例題練習
UVa 11183 - Teen Girl Squad
給定一張圖，求出最小生成樹。
UVa 11865 - Stream My Contest
給定有 個點和 條邊的網路，每條邊有起點、終點和寬頻，訊號會從點 傳送到其他地方，在建造成本最大為 的情況下，最多可達到多少寬頻速度?
二分搜寬頻速度 ， 代表只使用寬頻 的邊，建造成本是否 。