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之间已经兴建了路。
输出格式:
输出一行仅有一个整数，表示为使所有的村庄连通需要新建公路的长度的最小值。
输入样例:
1. 3 2. 0 990 692 3. 990 0 179 4. 692 179 0 5. 1 6. 1 2
结尾无空行
输出样例:
179
思路：把图转化为结构体存储，然后把已经存在的道路先添加进集合里面去，并把对应的边权置为零，然后排序把剩下的节点添加进去
#include<bits/stdc++.h> using namespace std; const int N=10100,inf=0x3f3f3f3f; int g[N][N],p[N]; int find(int x) { if(x!=p[x]) p[x]=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 k; cin>>k; while(k--) { 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; return 0; }
