题目大意：
现在已知一共有n(1<=n<=300)个宿舍，宿舍被数字1到n标记。一个宿舍有两种办法能用上Wi-Fi。一种是从其他宿舍链接网线，一种是自己去安装网络设备。自己安装网络设备需要花费w[i]，连接两个宿舍需要花费P[i][j] (连接i宿舍和j宿舍要花费P元)。

输入格式：
第一行：一个n
第二行到第n+1行：包含一个数w[i]；
第n+2行到2n+1行：第n+1+i行，每行n个数，第j个数表示P[i][j]

输出格式：
第一行：一个最小代价

样例：
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

输出：
9

题解： 和一般的最小模板题相比，最大区别就是自己对自己也有权，设置虚拟0点加上去，之后正常使用Kruskal（最小生成树）算法即可。
（其实必须得有一个自己对自己的权，这样更好理解，必须把0点也变为连通图里的一员！）

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>
using namespace std;
int n;
int fa[100005], rankk[100005], zi[100005];
int find(int x) {
	if (x == fa[x])return x;
	else return fa[x] = find(fa[x]);
}
struct edge{
	int u, v, w;
}ed[100005];
bool cmp(edge a, edge b) {
	return a.w < b.w;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for (int i = 0; i <= n; i++) {
		fa[i] = i;
	}
	for (int i = 1; i <= n; i++) {
		cin >> zi[i];
	}
	int index = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int xx; 
			cin >> xx;
			if (i == j) {
				ed[index].u = 0;
				ed[index].v = i;
				ed[index++].w = zi[i];
			}
			else {
				ed[index].u = i;
				ed[index].v = j;
				ed[index++].w = xx;
			}
		}
	}
	sort(ed , ed + index  ,cmp);
	int sum = 0; 
	for (int i = 0; i < index; i++) {
		int x = find(ed[i].u), y = find(ed[i].v);
		if (x != y) {
			fa[x] = y;
			sum += ed[i].w;
		}
	}
	cout << sum;
}