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

#include <algorithm>
#include <iostream>
#include <cstdio>
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;
}