POJ 1258 Agri-Net / HDU 暢通工程：最小生成樹 Prim 算法模板

題目大意

給定 N 個節點（農場/村莊）及其兩兩間的距離（或部分邊），求連通所有節點的最小總邊權（最小生成樹）。

• POJ 1258：輸入 N×N 邻接矩陣，N≤100。
• HDU 暢通工程：輸入 N(N-1)/2 條邊，N<100。

Prim 算法流程（鄰接矩陣版）

1. 初始化：dist[i] = INF，vis[i] = false。選 1 號點入樹，dist[1]=0。
2. 更新鄰居：對所有未入樹點 j，dist[j] = min(dist[j], mat[1][j])。
3. 重複 N-1 次：
   • 在未入樹點中找 dist[u] 最小的 u，加入樹，ans += dist[u]。
   • 用 u 更新其他未入樹點：dist[v] = min(dist[v], mat[u][v])。

代碼實現（適用兩題）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 105;
const int INF = 0x3f3f3f3f;

int mat[MAXN][MAXN];
int dist[MAXN];
bool vis[MAXN];

int prim(int n) {
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[1] = 0;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1, minVal = INF;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && dist[j] < minVal) {
                minVal = dist[j];
                u = j;
            }
        if (u == -1) return -1; // 不連通
        vis[u] = true;
        ans += dist[u];
        for (int v = 1; v <= n; v++)
            if (!vis[v] && mat[u][v] < dist[v])
                dist[v] = mat[u][v];
    }
    return ans;
}

int main() {
    int n;
    // POJ 1258: 讀矩陣
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                scanf("%d", &mat[i][j]);
        printf("%d\n", prim(n));
    }
    /* HDU 暢通工程: 讀邊列表
    while (scanf("%d", &n) == 1 && n) {
        memset(mat, 0x3f, sizeof(mat));
        for (int i = 1; i <= n*(n-1)/2; i++) {
            int a,b,c; scanf("%d%d%d",&a,&b,&c);
            mat[a][b] = mat[b][a] = c;
        }
        printf("%d\n", prim(n));
    }
    */
    return 0;
}

複雜度與優化

• 鄰接矩陣 Prim：O(N²)，N≤100 完全足夠。
• 若邊數較少（如 HDU），用鄰接表 + 優先隊列優化至 O(M log N)。

總結

最小生成樹是圖論基礎問題。Prim 算法適合稠密圖（矩陣），Kruskal 適合稀疏圖（邊表）。本題兩道皆為 Prim 矩陣版模板題，代碼極短，關鍵是正確讀入數據並初始化 dist 數組。