POJ 3206 最小生成樹完整解析：BFS 求最短路徑 + Prim 算法構建 MST

題目背景與核心思路

POJ 3206 要求連接地圖上所有的 'A'（外星人）與 'S'（起點），使總權值最小。本質是最小生成樹（MST）問題。解題分兩階段：

1. BFS 建圖： 從每個 'A'/'S' 點出發，廣度優先搜索計算到其他所有 'A'/'S' 的最短步數，構建完全圖的邊權矩陣。
2. Prim/Kruskal 求 MST： 在建立的完全圖上運行最小生成樹算法，得到最小總權值。

兩大關鍵坑點詳解

坑點 1：輸入處理的多餘空格

讀取 row 和 col 後，緩衝區殘留換行符。直接用 gets() 或 fgets() 讀取整行地圖字符串，而非逐字符 scanf("%c")，避免吞掉換行導致地圖數據錯位。

坑點 2：節點數組大小不足

題目說「最多 100 個外星人 + 1 個起點」，實際測試數據可能達到 102 個節點。數組 edge[102][102]、node[51][51] 必須開到 ≥102，否則越界導致 WA/RE。

核心代碼架構

BFS 建立邊權矩陣

void bfs(int si, int sj) {
    int dist[55][55] = {0};
    bool vis[55][55] = {false};
    queue> q;
    q.emplace(si, sj);
    vis[si][sj] = true;

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        if (node[x][y])  // 遇到另一個關鍵點
            edge[node[si][sj]][node[x][y]] = dist[x][y];

        for (auto [dx,dy] : dirs) {
            int nx = x+dx, ny = y+dy;
            if (inBound(nx,ny) && !vis[nx][ny] && map[nx][ny] != '#') {
                vis[nx][ny] = true;
                dist[nx][ny] = dist[x][y] + 1;
                q.emplace(nx, ny);
            }
        }
    }
}

Prim 算法求 MST

int prim(int n) {
    vector lowc(n+1, INF);
    vector vis(n+1, false);
    lowc[1] = 0;
    int ans = 0;

    for (int i = 1; i <= n; ++i) {
        int u = -1;
        for (int j = 1; j <= n; ++j)
            if (!vis[j] && (u==-1 || lowc[j] < lowc[u])) u = j;
        vis[u] = true;
        ans += lowc[u];
        for (int v = 1; v <= n; ++v)
            if (!vis[v] && edge[u][v] < lowc[v])
                lowc[v] = edge[u][v];
    }
    return ans;
}

完整流程主函數

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> col >> row;
        char dummy[20]; gets(dummy);  // 吃掉換行符

        memset(node, 0, sizeof(node));
        int cnt = 0;
        for (int i = 0; i < row; ++i) {
            gets(map[i]);
            for (int j = 0; j < col; ++j)
                if (map[i][j] == 'A' || map[i][j] == 'S')
                    node[i][j] = ++cnt;
        }

        memset(edge, 0x3f, sizeof(edge));
        for (int i = 0; i < row; ++i)
            for (int j = 0; j < col; ++j)
                if (node[i][j]) bfs(i, j);

        cout << prim(cnt) << endl;
    }
    return 0;
}

經驗總結

• BFS 時記錄距離而非步數，直接賦值給邊權矩陣。
• Prim 適用於稠密圖（本題完全圖），Kruskal 需先排序所有邊，反而較慢。
• 調試時可打印邊權矩陣驗證 BFS 正確性，排除建圖錯誤。