样题可见SYZOJ 最近发现最小生成树居然属于NOIP考察范围之内，就顺带膜了一发Kruscal。 Kruscal的主要思想就是贪心，这点感觉跟Dijkstra有点像，但是并不用进行堆优化之类的神奇的东西。。 其实挺简单的，比dinic不知道好写到哪里去了。

#include 
#include 
#include 
using namespace std;
const int MX = 305;
const int inf = 1000000007;
class edge {
public:
    int x, y, v;
}e[MX * MX];
int bing[MX], c[MX];
int n, tot;
int find_father(int x) {
    return x == bing[x] ? x : find_father(bing[x]);
}
bool cmp(edge a, edge b) {
    return a.v < b.v;
}
int kruscal() {
    sort(e + 1, e + tot + 1, cmp);
    int cnt = tot;
    int ans = 0;
    for (int i = 0; i <= n; i++) bing[i] = i;
    for (int i = 1; i <= tot; i++) {
        int f1 = find_father(e[i].x);
        int f2 = find_father(e[i].y);
        if (f1 != f2) {
            bing[f1] = f2;
            ans += e[i].v;
            cnt--;
            if (cnt == 1)   break;
        }
    }
    return ans;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
        e[++tot].x = 0;
        e[tot].y = i;
        e[tot].v = c[i];
    }
    int tmp;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &tmp);
            if (tmp) {
                e[++tot].x = i;
                e[tot].y = j;
                e[tot].v = tmp;
            }
        }
    }
    cout << kruscal() << endl;
}