给一个n个点的完全图 再给你m条道路已经修好 问你还需要修多长的路才能让所有村子互通
将给的m个点的路重新加权值为零的边到边集里 然后求最小生成树
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<string> 7 #define cl(a,b) memset(a,b,sizeof(a)) 8 #define debug(x) cerr<<#x<<"=="<<(x)<<endl 9 using namespace std; 10 typedef long long ll; 11 12 const int maxn=110; 13 14 int f[maxn],tol,n,m; 15 16 struct _edge 17 { 18 int u,v,w; 19 }edge[maxn*maxn*maxn]; 20 21 bool cmp(_edge a,_edge b) 22 { 23 return a.w<b.w; 24 } 25 26 void addedge(int u,int v,int w) 27 { 28 edge[tol].u=u; 29 edge[tol].v=v; 30 edge[tol].w=w; 31 tol++; 32 } 33 34 int _find(int x) 35 { 36 if(f[x]==-1) return x; 37 else return f[x]=_find(f[x]); 38 } 39 40 int kruskal() 41 { 42 cl(f,-1); 43 sort(edge,edge+tol,cmp); 44 int cnt=0,ans=0; 45 int u,v,w,f1,f2; 46 for(int i=0; i<tol; i++) 47 { 48 u=edge[i].u; 49 v=edge[i].v; 50 w=edge[i].w; 51 f1=_find(u); 52 f2=_find(v); 53 if(f1!=f2) 54 { 55 ans+=w; 56 f[f1]=f2; 57 cnt++; 58 } 59 if(cnt==n-1) break; 60 } 61 return ans; 62 } 63 64 int main() 65 { 66 while(scanf("%d",&n)!=EOF&&n) 67 { 68 tol=0; 69 for(int i=0;i<n;i++) 70 { 71 for(int j=0;j<n;j++) 72 { 73 int x; 74 scanf("%d",&x); 75 addedge(i,j,x); 76 } 77 } 78 scanf("%d",&m); 79 for(int i=0;i<m;i++) 80 { 81 int x,y; 82 scanf("%d%d",&x,&y); 83 addedge(x-1,y-1,0); 84 addedge(y-1,x-1,0); 85 } 86 printf("%d ",kruskal()); 87 } 88 return 0; 89 } 90 /* 91 92 3 93 0 990 692 94 990 0 179 95 692 179 0 96 1 97 1 2 98 99 */