HDU 1879 繼續暢通工程 (最小生成樹 Prim 算法)

問題描述

給定 N 個村莊 (1 < N < 100) 及其間所有可能道路的建設成本與是否已建成（1=已建，0=未建）。已建道路成本視為 0。求使所有村莊連通的最小總成本（即最小生成樹權重和）。多組測試，N=0 結束。

解法：Prim 算法

• 建立鄰接矩陣 mat[i][j]，已建道路權重設 0，未建設為給定成本。
• 從任意節點 (如 1) 開始，維護 dis[i] 表示非樹節點到樹的最小邊權。
• 每輪選擇 dis 最小的節點加入樹，更新答案並鬆弛鄰接邊。

關鍵代碼片段

void prim() {
    fill(vis, vis + n + 1, 0);
    for (int i = 1; i <= n; ++i) dis[i] = mat[1][i];
    vis[1] = 1; ans = 0;
    for (int i = 1; i < n; ++i) {
        int k = -1, minVal = INF;
        for (int j = 1; j <= n; ++j)
            if (!vis[j] && dis[j] < minVal) minVal = dis[k = j];
        vis[k] = 1; ans += minVal;
        for (int j = 1; j <= n; ++j)
            if (!vis[j] && mat[k][j] < dis[j]) dis[j] = mat[k][j];
    }
}

輸入優化

邊數達 N(N-1)/2 ≈ 5000，使用 scanf 而非 cin 避免超時。

範例

輸入：
3
1 2 1 0
1 3 2 0
2 3 4 0
3
1 2 1 0
0

輸出：
3
1

解析：第一組三條路皆未建，選擇成本 1 和 2 的邊，總和 3；第二組 1-2 已建（成本 0），只需建 1-3 成本 1。