【hdu 1233】还是畅通工程

xiaoxiao2021-02-27  122

还是畅通工程

  某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。  Input 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。  当N为0时,输入结束,该用例不被处理。  Output 对每个测试用例,在1行里输出最小的公路总长度。  Sample Input 3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0 Sample Output 3 5 Huge input, scanf is recommended. Hint Hint 代码: #include<cstdio> #include<algorithm> #include<string.h> using namespace std; int n,m,i,j,root,length,ans; int par[5000]; struct rode { int st,endd; int distance; }date[5000]; bool cmp(rode a,rode b) { return a.distance<b.distance; } int find(int x) { int q=x; while(x!=par[x]) x=par[x]; while(par[q]!=x) { int j=par[q]; par[q]=x; q=j; } return x; } void join(int x,int y) { int fx,fy; fx=find(x); fy=find(y); if(fx!=fy) par[fx]=fy; } int main() { while(~scanf("%d",&n)&&n) { length=0; ans=0; m=n*(n-1)/2; for(i=1;i<=m;i++) { par[i]=i; } for(i=1;i<=m;i++) { scanf("%d%d%d",&date[i].st,&date[i].endd,&date[i].distance); } sort(date+1,date+m+1,cmp); for(i=1;i<=m;i++) { int u=date[i].st;// 注意 int v=date[i].endd;//注意 if(find(u)!=find(v)) { join(u,v); ans++; length+=date[i].distance; } if(ans==n-1) break; } printf("%d\n",length); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-16000.html

最新回复(0)