「Bzoj 1601」「Usaco2008 Oct」灌水 (最小生成树)

BZOJ 1601
Luogu 1550
最小生成树上的花费最小。但是这里还有开井的费用，怎么办?我们设一个0点到所有连边，边权为开井的费用，那么就可以最小生成树求解了

想算法的时候多思考一下算法的正确性，多试试样例，想一下极端情况，不要直接就开始编写程序。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 300 + 5, MAXM = 200000 + 5;
struct data {
    int u, v, wi;
    bool operator < (const data &b) const {
        return wi < b.wi;
    }
}e[MAXM];
int en, wi[MAXN], n, f[MAXN];
int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}
void clean() {
    en = 0;
    for (int i=1;i<=n;i++) f[i] = i;
}
void solve() {
    clean();
    for (int i=1;i<=n;i++) {
        scanf("%d", &wi[i]);
        en++, e[en].u = 0, e[en].v = i, e[en].wi = wi[i];
    }
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) {
            int x; scanf("%d", &x);
            if (j > i) {
                en++, e[en].u = i, e[en].v = j, e[en].wi = x;
            }
        }
    }
    sort(e + 1, e + 1 + en);
    int tot = 0;
    for (int i=1;i<=en;i++) {
        int x = find(e[i].u), y = find(e[i].v);
        if (x != y) f[x] = y, tot += e[i].wi;
    }
    printf("%d\n", tot);
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    scanf("%d", &n), solve();
    return 0;
}