「USACO 2008」灌水

题目大意：灌 $n$ 块农田，把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库。建造一个水库需要花费 $w_i$，连接两块土地需要花费 $p_{i,j}$，计算所需的最少代价。$n \leq 300$

建超级源点 $S$，每个点向 $S$ 连 $w_i$ 的边，最小生成树。

#include <cstdio>
#include <algorithm>
 
struct Edge {
    int u, v, w;
    bool operator < (const Edge rhs) const {
        return w < rhs.w;
    }
} e[50000];
 
int fa[305], tot, ans;
 
int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
int find(int x) {
    if (x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
void kruskal() {
    std::sort(e + 1, e + tot + 1);
    for (int i = 1; i <= tot; ++i) {
        int fx = find(e[i].u), fy = find(e[i].v);
        if (fx == fy) continue;
        fa[fx] = fy, ans += e[i].w;
    }
}
 
int main() {
    int n = read();
    for (int i = 1; i <= n; ++i)
        e[++tot] = (Edge){0, i, read()};
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            int k = read();
            if (i < j) e[++tot] = (Edge){i, j, k};
        }
    for (int i = 1; i <= n; ++i) fa[i] = i;
    kruskal();
    printf("%d\n", ans);
    return 0;
}

时间复杂度 $O(m\log m)$