HDU 1102 Constructing Roads：已有邊條件下的最小生成樹 (Prim 算法)

問題描述

給定 n (≤ 100) 個村莊的鄰接矩陣 map[i][j] (距離)，及 m 條**已建成道路** (權重視為 0)。求在現有基礎上**新增道路的最小總長度** 使所有村莊連通。多測試用例，EOF 結束。

算法思路：Prim 算法 + 權重預處理

• 讀入鄰接矩陣。
• 讀入 m 條已有道路 (x,y)，**將對應矩陣權重設為 0** (map[x-1][y-1] = map[y-1][x-1] = 0)。
• 直接在修改後的矩陣上跑 Prim 算法，得到的 MST 權重和即為**需新建道路總長度** (因已有路權重 0 不計入成本)。

完整代碼 (C)

#include 
#include 
#include 

#define MAXN 101
#define INF 0x3f3f3f3f

int n;
int graph[MAXN][MAXN];
int minDist[MAXN];
int visited[MAXN];

void resetGraph(int n) {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            scanf("%d", &graph[i][j]); // 直接讀入矩陣

    int m; scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        int x, y; scanf("%d %d", &x, &y);
        --x; --y; // 1-based -> 0-based
        graph[x][y] = graph[y][x] = 0; // 已有路權重歸零
    }
}

int prim(int n) {
    for (int i = 0; i < n; ++i) {
        minDist[i] = INF;
        visited[i] = 0;
    }
    minDist[0] = 0;
    int sum = 0;

    for (int i = 0; i < n; ++i) {
        int u = -1;
        for (int j = 0; j < n; ++j)
            if (!visited[j] && (u == -1 || minDist[j] < minDist[u]))
                u = j;

        visited[u] = 1;
        sum += minDist[u];

        for (int v = 0; v < n; ++v)
            if (!visited[v] && graph[u][v] < minDist[v])
                minDist[v] = graph[u][v];
    }
    return sum;
}

int main() {
    while (scanf("%d", &n) == 1) {
        resetGraph(n);
        printf("%d\n", prim(n));
    }
    return 0;
}

關鍵技巧總結

正確性證明

MST 性質：對於任意圖，給定某些邊**強制納入** (或權重設為 0)，在剩餘邊中求 MST，等價於在修改權重後的圖上求標準 MST。因 0 權重邊必被貪心策略優先選中 (不構成環時)，且不增加目標函數值。

複雜度

• 時間：O(n²) = 10⁴，極快。
• 空間：O(n²) 矩陣。

Kruskal 替代實現

• 將矩陣展開為邊列表 (含 0 權重邊)。
• 按權重排序，並查集合並。
• 優先處理 0 權重邊 (已建路)，再處理正權重邊。
• 代碼較長但邏輯同樣清晰。