最小樹形圖 (DMST) 朱劉算法 C++ 模板完整解析

問題定義

給定一個有向圖 G=(V,E)、根節點 root、邊權 cost。尋找一棵以 root 為根的有向生成樹，使得所有節點可從根到達，且邊權總和最小。即 Directed Minimum Spanning Tree (DMST)，又稱 最小樹形圖。

朱劉算法核心邏輯 (O(E·V))

1. 縮點：對每個非根節點選入權最小的入邊，形成若干環
2. 環處理：將每個環縮為一個超級節點，調整進入環的邊權：new_cost = old_cost - in_edge_cost_of_target
3. 遞歸求解：在縮點後的圖上重複上述過程，直到無環
4. 展開：逆序展開縮點，還原具體邊集

完整 C++ 模板 (節點 0~V-1)

#include 
using namespace std;

const int MAXV = 110;          // 最大節點數
const int MAXE = MAXV * MAXV;  // 最大邊數
const int INF = 1 << 30;

struct Edge {
    int u, v, cost;
} E[MAXE];

int pre[MAXV], ID[MAXV], vis[MAXV], In[MAXV];
int V, E_cnt, root;

int dmst(int root, int N, int M) {
    int ret = 0;
    while (true) {
        // 1. 初始化入邊權為 INF
        fill(In, In + N, INF);
        // 2. 找每個節點最小入邊 (排除自環)
        for (int i = 0; i < M; ++i) {
            if (E[i].u != E[i].v && E[i].cost < In[E[i].v]) {
                pre[E[i].v] = E[i].u;
                In[E[i].v] = E[i].cost;
            }
        }
        // 3. 檢查是否有節點(除根)無入邊 -> 無解
        for (int i = 0; i < N; ++i) {
            if (i == root) continue;
            if (In[i] == INF) return -1; // 不連通
        }

        // 4. 找環 & 縮點
        int cnt = 0;
        fill(ID, ID + N, -1);
        fill(vis, vis + N, -1);
        In[root] = 0; // 根節點入邊權歸零，不計入答案

        for (int i = 0; i < N; ++i) {
            ret += In[i];
            int v = i;
            // 沿 pre 指針尋找環
            while (vis[v] != i && ID[v] == -1 && v != root) {
                vis[v] = i;
                v = pre[v];
            }
            // 發現環 (v != root 且 ID[v] 未分配)
            if (v != root && ID[v] == -1) {
                // 將環上所有節點標記為同一超級節點 cnt
                for (int u = pre[v]; u != v; u = pre[u])
                    ID[u] = cnt;
                ID[v] = cnt++;
            }
        }
        if (cnt == 0) break; // 無環，算法結束

        // 5. 非環節點分配新 ID
        for (int i = 0; i < N; ++i)
            if (ID[i] == -1) ID[i] = cnt++;

        // 6. 重建邊集：調整進入環的邊權
        for (int i = 0; i < M; ++i) {
            int u = E[i].u, v = E[i].v;
            E[i].u = ID[u];
            E[i].v = ID[v];
            if (E[i].u != E[i].v)
                E[i].cost -= In[v]; // 關鍵：減去目標節點原最小入邊權
        }

        N = cnt;
        root = ID[root];
    }
    return ret;
}

// 使用示例
int main() {
    // 輸入: V, E, root
    // 邊列表: u v cost
    // 調用 dmst(root, V, E_cnt)
}

關鍵細節圖解

入邊選擇與環形成

原圖:          選最小入邊後:        發現環 1->2->3->1:
  5                  5                    5
→ → →           → → →              → → →
1 ← 2           1 ← 2              1 ← 2
↑   ↓   4       ↑   ↓   4          ↑   ↓   4
3 → 4           3 → 4              3 → 4

邊權調整公式推導

環內節點 v 原最小入邊權 In[v] 已計入答案。外部邊 u→v 若被選中，需替換掉 In[v]，故新權重 = cost(u→v) - In[v]。這保證了在縮點圖上選擇該邊的增量成本正確。

常見坑點

1. 節點編號必須 0~V-1，算法直接用作數組下標
2. 必須去除自環 (u != v)，否則干擾最小入邊選擇
3. 根節點無入邊，In[root]=0 且不參與環檢測
4. 多重邊：保留最小權重即可，或算法自然處理
5. 無解判斷：除根外存在 In[i]==INF 節點，返回 -1

應用場景

• 網絡路由優化 (以某節點為根的最小成本廣播樹)
• 編譯器優化 (指令調度依賴圖)
• 項目管理 (任務依賴最小成本關鍵路徑)
• 生物信息學 (系統發育樹重建)

複雜度與優化

總結

朱劉算法是解決有向圖最小生成樹的經典算法，核心思想是貪心選最小入邊 + 環縮點 + 權重補償。模板代碼簡潔高效，是 ACM/ICPC 及工程落地的必備組件。理解 cost -= In[v] 的幾何意義 (替換成本) 是掌握該算法的關鍵。