题目
YYH拿到了父亲给的钱欣喜若狂，把这些钱拿来造了n栋房子。现在他要给这些房子通电。他有两种方法：第一种是在房间里搭核电发电机发电，对于不同的房子，他需要花不同的代价Vi；，第二种是将有电的房子i的电通过电线通到没电的房子j中，这样子他需要花的代价为aij。他现在请你帮他算出他最少要花多少钱才能让所有的房子通上电。
输入格式：
第一行为一个整数 n。接下来的n行为 n 个整数vi，再接下来的n行每行n个数，第i行第j列的数表示aij。
输出格式：
一个整数，表示最小代价。
样例输入：
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
样例输出：
9
题解
把用核电发电机发电的房子看作与一个有电的0号房子相连，用最小生成树解决。（看懂了题目，就觉得其实挺水的……）
数据范围很小，直接Kruskal或者Prim都行。
代码
#define FileIO(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 305
int n,m=,f[N];
struct edge{int s,t,w;}e[];
int find(int x) {
return ~f[x]?f[x]=find(f[x]):x;
}
inline bool join(int a,int b) {
int x=find(a),y=find(b);
if(x==y) return false;
f[x]=y;return true;
}
bool cmp(edge a,edge b) {
return a.w<b.w;
}
int kruskal() {
int cnt=n,ans=;
memset(f,~,sizeof(f));
std::sort(e,e+m,cmp);
for(int i=;i<m;++i) {
if(join(e[i].s,e[i].t)) {
ans+=e[i].w;
if(!--cnt) return ans;
}
}
return -;
}
int main() {
FileIO("zzi");
int a;
scanf("%d",&n);
for(int i=;i<=n;++i) {
scanf("%d",&a);
e[m++]={,i,a};
}
for(int i=;i<=n;++i) {
for(int j=;j<=n;++j) {
scanf("%d",&a);
if(i<j) e[m++]={i,j,a};
}
}
printf("%d",kruskal());
return ;
}
Code