POJ 1258 Agri-Net：普林姆算法求最小生成樹 (MST) 模板題

題目背景

給定 N (3 ≤ N ≤ 100) 個農場及其兩兩距離矩陣（對稱，對角線為 0），求連接所有農場的最小光纖總長度，即完全圖的最小生成樹權值和。多測試案例，輸入至 EOF。

普林姆算法核心思想

維護一個集合 U（已加入 MST 的頂點），初始包含任一頂點（如 0）。重複 N-1 次：

1. 在 V \ U 中找距離 U 最近的頂點 v（即 min{dist[v]}）。
2. 將 v 加入 U，累加 dist[v] 到答案。
3. 用 v 更新其餘頂點到 U 的最短距離：dist[u] = min(dist[u], w[v][u])。

關鍵數據結構

• dist[i]：頂點 i 到當前 MST 的最短距離。
• used[i]：頂點是否已在 MST 中。
• 鄰接矩陣 w[i][j] 存儲邊權。

完整 C++ 實現

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;
int w[MAXN][MAXN], dist[MAXN];
bool used[MAXN];

int main() {
    int n;
    while (cin >> n) {
        memset(used, 0, sizeof(used));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> w[i][j];
        // 初始化
        used[0] = true;
        for (int i = 1; i < n; i++) dist[i] = w[0][i];
        dist[0] = INF;
        int ans = 0;
        for (int iter = 1; iter < n; iter++) {
            int v = -1, minD = INF;
            for (int i = 0; i < n; i++)
                if (!used[i] && dist[i] < minD) {
                    minD = dist[i];
                    v = i;
                }
            used[v] = true;
            ans += minD;
            for (int i = 0; i < n; i++)
                if (!used[i]) dist[i] = min(dist[i], w[v][i]);
        }
        cout << ans << endl;
    }
    return 0;
}

複雜度與優化

• 時間：O(N²)，N ≤ 100 完全足夠。稀疏圖可用堆優化至 O(E log V)，但此題為稠密圖，矩陣版最簡潔。
• 空間：O(N²) 存矩陣。

常見錯誤提醒

1. dist[0] 初始化為 INF 而非 0，否則會錯誤選回已加入的頂點。
2. 多測試案例需完整重置數組（used, dist）。
3. 輸入可能跨行（矩陣元素不一定每行 N 個），用 cin 或 scanf 自動處理空白。

克魯斯克爾對比

同樣可用 Kruskal + 並查集，但需生成所有邊（~5000 條），排序 O(E log E) 略慢於 O(N²) Prim。本題 Prim 更優。