题意:给出每两个城市间建路的花费和已经拥有的路,求最小花费让图连通。
最小生成树。。
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxv=105,maxe=10005; struct node { int w,to,next,f; } e[maxe]; int head[maxv],dis[maxv],p[maxv],edge,n; void add(int u,int v,int c) { e[edge].f=v,e[edge].to=u,e[edge].w=c,e[edge].next=head[u],head[u]=edge++; } int cmp(node a,node b) { return a.w<b.w; } int find(int x) { return p[x]==x?x:p[x]=find(p[x]); } int kru() { int ans=0; for(int i=0; i<n; i++) p[i]=i; sort(e,e+edge,cmp); for(int i=0; i<edge; i++) { int x=find(e[i].f),y=find(e[i].to); if(x!=y)ans+=e[i].w,p[x]=y; } return ans; } int main() { int q,val; while(~scanf("%d",&n)) { edge=0; for(int i=0; i<n; i++) for(int j=0; j<n; j++) { scanf("%d",&val); if(i!=j) add(i,j,val); } scanf("%d",&q); for(int i=0; i<q; i++) { int u,v; scanf("%d%d",&u,&v); for(int j=0; j<edge; j++) if((e[j].f==u-1&&e[j].to==v-1)||(e[j].f==v-1&&e[j].to==u-1)) e[j].w=0; } printf("%d\n",kru()); } return 0; }