HDU 1102：構建道路——最小生成樹變體

題目描述

N 個村莊（N ≤ 100），給出任意兩村之間修路成本矩陣。Q 條已建道路（成本視為 0）。求連通所有村莊的最小額外成本。

關鍵技巧：已建道路成本設為 0

直接在成本矩陣中將已建道路雙向設置為 0，然後跑標準 Prim 算法，自動優先選擇 0 成本邊，等價於先連通已有道路再補充。

Prim 算法實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105, INF = 1<<28;
int cost[N][N], mincost[N];
bool used[N];
int n, q;

void prim() {
    fill(mincost, mincost+N, INF);
    memset(used, 0, sizeof(used));
    mincost[1] = 0;
    int ans = 0;
    while (true) {
        int v = -1;
        for (int i = 1; i <= n; ++i)
            if (!used[i] && (v == -1 || mincost[i] < mincost[v])) v = i;
        if (v == -1) break;
        used[v] = true;
        ans += mincost[v];
        for (int i = 1; i <= n; ++i)
            mincost[i] = min(mincost[i], cost[v][i]);
    }
    printf("%d\n", ans);
}

int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                scanf("%d", &cost[i][j]);
        scanf("%d", &q);
        for (int i = 0, a, b; i < q; ++i) {
            scanf("%d%d", &a, &b);
            cost[a][b] = cost[b][a] = 0;
        }
        prim();
    }
    return 0;
}

複雜度

• 時間：O(N²) —— 稠密圖 Prim 最優
• 空間：O(N²) 存儲矩陣

注意

• 輸入多組測試，EOF 結束
• 村莊編號從 1 開始
• 成本矩陣對稱