POJ 1258 Agri-Net：最小生成樹 Prim 算法模板題

問題描述

給定 N（≤ 100）個農場，及其兩兩之間的距離矩陣（對角線為 0，對稱）。求連接所有農場的最小光纖總長度（即最小生成樹權值和）。

Prim 算法實現

稠密圖適用 Prim O(N^2)。維護 low[i] 為節點 i 到當前樹的最小邊權，vis[i] 標記是否已入樹。每輪選未入樹的最小 low 節點加入，更新鄰居 low。

代碼（兩種寫法）

// 寫法一：初始化 low 為 1 號點的邊
void prim() {
    int sum = 0;
    for (int i = 1; i <= n; i++) { low[i] = Map[1][i]; vis[i] = 0; }
    vis[1] = 1;
    for (int i = 1; i <= n; i++) {
        int Min = INF, pos = -1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && low[j] < Min) { Min = low[j]; pos = j; }
        if (pos == -1) break;
        vis[pos] = 1; sum += Min;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && Map[pos][j] < low[j]) low[j] = Map[pos][j];
    }
    printf("%d\n", sum);
}

注意事項

• 輸入矩陣可能跨行，用 scanf 直接讀整數無視換行。
• 多測試用例，以 EOF 結束。
• N=100 時 O(N^2) 極快，無需優化堆版 Prim。