7-14 修建道路 (10 分)
N个村庄，从1到N编号，现在请您兴建一些路使得任何两个村庄彼此连通。我们称村庄A和B是连通的，当且仅当在A和B之间存在一条路，或者存在一个存在C，使得A和C之间有一条路，并且C和B是连通的。
已知在一些村庄之间已经有了一些路，您的工作是再兴建一些路，使得所有的村庄都是连通的，并且兴建的路的长度是最小的。
输入格式:
第一行是一个整数N（3<=N<=100），代表村庄的数目。后面的N行，第i行包含N个整数，这N个整数中的第j个整数是第i个村庄和第j个村庄之间的距离，距离值在[1,1000]之间。
然后是一个整数Q(0<=Q<=N*(N+1)/2)。后面给出Q行，每行包含两个整数a和b（1<=a<b<=N），表示在村庄a和b之间已经兴建了路。
输出格式:
输出一行仅有一个整数，表示为使所有的村庄连通需要新建公路的长度的最小值。
输入样例:
3 0 990 692 990 0 179 692 179 0 1 1 2
结尾无空行
输出样例:
179
结尾无空行
#include<bits/stdc++.h> using namespace std; const int N=10100; int g[N][N],p[N]; int find(int x){ if(x!=p[x])p[x]=find(find(p[x])); return p[x]; } struct node{ int x,y,w; }s[N]; bool cmp(node a,node b){ return a.w<b.w; } int main(){ int n,cnt=0,ans=0; cin>>n; for(int i=1;i<=n;i++)p[i]=i; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>g[i][j]; int m; cin>>m; while(m--){ int a,b; cin>>a>>b; p[find(a)]=find(b); g[a][b]=g[b][a]=0; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(g[i][j]){ s[cnt].x=i; s[cnt].y=j; s[cnt].w=g[i][j]; cnt++; } } } sort(s,s+cnt,cmp); for(int i=0;i<cnt;i++){ if(find(s[i].x)!=find(s[i].y)&&g[s[i].x][s[i].y]){ p[find(s[i].x)]=s[i].y; ans+=s[i].w; } }cout<<ans<<endl; return 0; }
