您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 3164 Command Network 與 UVA 11183 Teen Girl Squad：最小樹形圖算法詳解

編輯：關於C++

最小樹形圖（Minimum Arborescence）核心概念

最小樹形圖是有向圖中從指定根節點出發，能到達所有節點的最小成本有向生成樹。求解步驟如下：

對每個非根節點，選取入邊權重最小的邊構成邊集 E₀。
若某節點無入邊，則不存在最小樹形圖。
若 E₀ 不含有向環，則 E₀ 即為最小樹形圖的所有邊。
若 E₀ 含有向環，將每個環縮縮為一個超級節點，調整邊權重，構造新圖 G₁，遞歸求解直到無環為止，再逐層展開還原得到原圖的最小樹形圖。

UVA 11183 Teen Girl Squad 題目分析

題目背景：n 位少女（編號 0~n-1，你是 0 號）需透過手機傳遞消息。已知 m 條有向邊 u→v 及其費用 w，表示 u 可撥打 v 的費用。目標是從 0 號開始，以最小總成本讓消息傳達給所有其他人。這正是以 0 為根的最小樹形圖問題。

輸入輸出格式

多測試案例，每案例給出 n（≤1000）和 m（≤40000）。
輸出 "Case #x: 最小成本" 或 "Case #x: Possums!"（無解）。

樣例解析

4
2
1
0 1 10
2
1
1 0 10
4
4
0 1 10
0 2 10
1 3 20
2 3 30
4
4
0 1 10
1 2 20
2 0 30
2 3 100

Case #1: 10
Case #2: Possums!
Case #3: 40
Case #4: 130

朱劉算法（Zhu-Liu Algorithm）C++ 實現要點

核心函數 zhuliu(root, n, m, edges) 返回最小成本，若不存在返回 -1。關鍵步驟：

初始化每個節點的最小入邊 in[i]。
檢查是否有節點（除根外）無入邊 → 返回 -1。
找環、縮環、調整邊權、遞歸/迭代求解。
最終累加所有 in[i] 即為答案。

完整代碼示例

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
const int maxn = 1010;
const int INF = 0x3f3f3f3f;
const int maxm = 40010;

struct Edge {
    int u, v, cost;
} edge[maxm];

int pre[maxn], id[maxn], vis[maxn], in[maxn];

int zhuliu(int root, int n, int m, Edge edge[]) {
    int u, v;
    int res = 0;
    while (1) {
        for (int i = 0; i < n; i++) in[i] = INF;
        // 1. 找每個點最小入邊
        for (int i = 0; i < m; i++) {
            u = edge[i].u; v = edge[i].v;
            if (edge[i].cost < in[v] && u != v) {
                pre[v] = u;
                in[v] = edge[i].cost;
            }
        }
        // 2. 檢查是否有點無入邊（除根）
        for (int i = 0; i < n; i++) {
            if (i == root) continue;
            if (in[i] == INF) return -1;
        }
        // 3. 找環並縮縮
        int cnt = 0;
        memset(id, -1, sizeof(id));
        memset(vis, -1, sizeof(vis));
        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 u = pre[v]; u != v; u = pre[u])
                    id[u] = cnt;
                id[v] = cnt++;
            }
        }
        if (cnt == 0) break; // 無環
        for (int i = 0; i < n; i++)
            if (id[i] == -1) id[i] = cnt++;
        // 4. 調整邊權重建新圖
        for (int i = 0; i < m; i++) {
            u = edge[i].u; v = edge[i].v;
            edge[i].u = id[u];
            edge[i].v = id[v];
            if (edge[i].u != edge[i].v)
                edge[i].cost -= in[v];
        }
        n = cnt;
        root = id[root];
    }
    return res;
}

int main() {
    int T, n, m;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; i++)
            scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost);
        int ans = zhuliu(0, n, m, edge);
        if (ans == -1)
            printf("Case #%d: Possums!\n", cas);
        else
            printf("Case #%d: %d\n", cas, ans);
    }
    return 0;
}