记录编号	406041	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 挖水井	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.061 s
提交时间	2017-05-17 19:59:05	内存使用	1.72 MiB

# include <bits/stdc++.h>
# define MAXN 303
using namespace std;
inline int gn() {
	int k = 0;
	char c = getchar();
	for(; !isdigit(c); c = getchar());
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k;
}
int head[MAXN << 1], cnt, n, b[MAXN];
struct edge {
	int fr, to, w, ne;
	inline edge() {;}
	inline edge(int fr_, int to_, int w_, int ne_) {
		fr = fr_, to = to_, w = w_, ne = ne_;
	}
}e[MAXN * MAXN];
inline bool cmp(edge a, edge b) {
	return a.w < b.w;
}
inline void addedge(int fr, int to, int w) {
	e[++cnt] = edge(fr, to, w, head[fr]), head[fr] = cnt;
	//e[++cnt] = edge(to, fr, w, head[to]), head[to] = cnt;
}
bool alr[MAXN];
int fa[MAXN];
int find(int x) {
	if(x == fa[x]) return x;
	else {
		fa[x] = find(fa[x]);
		return fa[x];
	}
}
inline void merge(int x, int y) {
	x = find(x), y = find(y);
	if(x != y) fa[y] = x;
}
inline int KRUSCAL() {
	int ans = 0, k = 0;
	for(int i = 1; i <= n; i++) fa[i] = i;
	sort(e + 1, e + 1 + cnt, cmp);
	for(int i = 1; i <= cnt; i++) {
		int u = e[i].fr;
		int v = e[i].to;
		if(find(u) != find(v)) {
			merge(u, v);
			ans += e[i].w;
			k++;
		}
		if(k == n) break;
	}
	return ans;
}
int main() {
	freopen("water.in", "r", stdin);
	freopen("water.out", "w", stdout);
	n = gn();
	for(int i = 1; i <= n; i++) {
		b[i] = gn();
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			int k = gn();
			if(j > i) addedge(i, j, k);
		}
	}
	for(int i = 1; i <= n; i++) {
		addedge(i, n + 1, b[i]);
	}
	cout << KRUSCAL();
}