题目：打井
思路：
现在图中加入一个节点0，并向1~n引出一条权值为wi的边。
这样就相当于默认在节点0打井了，在新图中求出最小生成树就好。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 300struct Edge{int x,y,z;Edge(){}Edge(int xx,int yy,int zz) {x=xx,y=yy,z=zz;}bool operator < (const Edge& oth) const {return z<oth.z;}
};int n;
vector<Edge> e;
int fa[maxn+5]={
0};void readin(){scanf("%d",&n);for(int i=1;i<=n;i++) {int x;scanf("%d",&x);e.push_back(Edge(0,i,x));}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int x;scanf("%d",&x);if(j<=i) continue;else e.push_back(Edge(i,j,x));}}
}int find(int x){if(-1==fa[x]) return x;else return fa[x]=find(fa[x]);
}void init(){sort(e.begin(),e.end());memset(fa,-1,sizeof(fa));
}int kruskal(){init();int ans=0;for(int i=0;i<e.size();i++) {int x=e[i].x,y=e[i].y;int f1=find(x),f2=find(y);if(f1==f2) continue;else fa[f1]=f2;ans+=e[i].z;}return ans;
}int main(){readin();int ans=kruskal();printf("%d",ans);return 0;
}