POJ 2784 Buy or Build：最小生成樹與子網絡購買策略

題目簡介

有 n 個城市（n ≤ 1000）和 q 個現有子網絡（q ≤ 8）。每個子網絡包含若干城市，購買成本固定，不可拆分。若不購買子網絡，任兩城市間建邊成本為歐氏距離平方。求連接所有城市的最小總成本。

題目連結：POJ 2784

解題思路

由於 q ≤ 8，子網絡購買組合最多 2^8 = 256 種，可用狀態壓縮枚舉所有購買方案：

1. 枚舉所有子網絡購買子集（狀態 0 到 2^q - 1）。
2. 對於每個子集，計算固定購買成本，並用並查集合併該子集包含的所有城市。
3. 在剩餘未連通的城市之間，按歐氏距離平方建立所有可能的邊，運行 Kruskal 算法求最小生成樹補全連通。
4. 取所有方案中的最小總成本。

代碼實現

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1009;
int fa[N], x[N], y[N];
int cost[9], mcnt[9], sub[9][N];
int n, q;

struct Edge { int u, v; double w; };
bool operator<(Edge a, Edge b) { return a.w < b.w; }

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

double kruskal() {
    vector edges;
    for (int i = 1; i <= n; i++)
        for (int j = i+1; j <= n; j++)
            if (find(i) != find(j)) {
                double dx = x[i]-x[j], dy = y[i]-y[j];
                edges.push_back({i, j, dx*dx + dy*dy});
            }
    sort(edges.begin(), edges.end());
    double sum = 0;
    for (auto &e : edges) {
        int fu = find(e.u), fv = find(e.v);
        if (fu != fv) {
            fa[fu] = fv;
            sum += e.w;
        }
    }
    return sum;
}

int main() {
    while (cin >> n >> q) {
        for (int i = 1; i <= q; i++) {
            cin >> mcnt[i] >> cost[i];
            for (int j = 1; j <= mcnt[i]; j++) cin >> sub[i][j];
        }
        for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
        double ans = 1e18;
        for (int mask = 0; mask < (1<

複雜度分析
枚舉 2^q 種方案，每次 Kruskal 處理 O(n^2 log n) 邊。總複雜度 O(2^q × n^2 log n)，q ≤ 8 時可行。