POJ 3164 最小樹形圖：Chu-Liu/Edmonds 算法模板題

題目

有向圖 n 點 m 邊，點 1 為根，邊權為歐氏距離。求以根為根的最小樹形圖 (有向最小生成樹) 權值和，不存在輸出 "poor snoopy"。

Zhuliu 算法流程

1. 每點選入邊：對每個非根節點，選入邊權最小的入邊。若某點無入邊 → 無解。
2. 找環：沿入邊回溯，標記訪問順序，發現環則縮點。
3. 縮點重構：環內節點合併為超級節點，調整邊權：w'(u,v) = w(u,v) - in[v] (v 為環內節點)。
4. 遞歸求解：在縮點圖上重複上述步驟，直到無環。累加每輪入邊權和即為答案。

核心代碼片段

double zhuliu(int root, int n, int m, Edge edges[]) {
    double res = 0;
    while (true) {
        // 1. 選入邊
        fill(in, in+n, INF);
        for (int i = 0; i < m; ++i)
            if (edges[i].u != edges[i].v && edges[i].cost < in[edges[i].v]) {
                pre[edges[i].v] = edges[i].u;
                in[edges[i].v] = edges[i].cost;
            }
        // 檢查可達性
        for (int i = 0; i < n; ++i)
            if (i != root && in[i] == INF) return -1;
        // 2. 找環並縮點
        int cnt = 0;
        fill(id, id+n, -1); fill(vis, vis+n, -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 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++;
        // 3. 重構邊
        for (int i = 0; i < m; ) {
            int v = edges[i].v;
            edges[i].u = id[edges[i].u];
            edges[i].v = id[edges[i].v];
            if (edges[i].u != edges[i].v) edges[i++].cost -= in[v];
            else swap(edges[i], edges[--m]);
        }
        n = cnt; root = id[root];
    }
    return res;
}

本題具體處理

• 讀入點座標，建立完全圖邊權 = 歐氏距離。
• 再讀 m 條限制邊，取最小權值更新對應邊 (可能有重邊)。
• 調用 zhuliu(0, n, edge_cnt, edges)，根節點 0 對應原 1 號點。

複雜度

• 時間：O(n·m) —— 每輪縮點至少減少一個節點，共 ≤ n 輪，每輪掃描所有邊。
• 空間：O(n + m)