样题可见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 > 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;
}