POJ 2421 Constructing Roads 預連接邊的 MST

題目變體

標準 MST 問題，但輸入中給出 m 條已建成的道路（必須保留）。求補全連通圖的最小額外代價。

技巧：預連接邊權值設 0

• 將已建道路對應的邊權值設為 0
• 運行標準 Kruskal/Prim
• 這些邊必會優先被選入 MST（權值最小），且不增加總代價
• 最終 MST 總權值即為需新建道路的最小代價

代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 110;
const int MAXE = 10000;

struct Edge { int u, v, w; bool operator<(Edge o) const { return w < o.w; } };
Edge edges[MAXE];
int parent[MAXN];
bool built[MAXN][MAXN];
int dist[MAXN][MAXN];

int findSet(int x) { return parent[x]==x ? x : parent[x]=findSet(parent[x]); }

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                scanf("%d", &dist[i][j]);

        memset(built, 0, sizeof(built));
        int m; scanf("%d", &m);
        while (m--) { int x,y; scanf("%d%d",&x,&y); built[x][y]=built[y][x]=1; }

        int ecnt = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = i+1; j <= n; ++j)
                edges[ecnt++] = {i, j, built[i][j] ? 0 : dist[i][j]};

        sort(edges, edges+ecnt);
        for (int i = 1; i <= n; ++i) parent[i] = i;

        int ans = 0, cnt = 0;
        for (int i = 0; i < ecnt && cnt < n-1; ++i) {
            int u = edges[i].u, v = edges[i].v, w = edges[i].w;
            int ru = findSet(u), rv = findSet(v);
            if (ru != rv) {
                parent[ru] = rv;
                ans += w;
                ++cnt;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

複雜度

• 邊數 O(N²)，N≤100 時 ≤4950
• Kruskal：O(E log E) ≈ 5e4 操作，極快

關鍵點總結

• 「必選邊」轉化為「權值 0」是經典技巧
• 並查集路徑壓縮優化
• 多測試案例，EOF 結束