杭电1233
本题首先要判断两个村庄距离是否最短,其次,两村庄是否联通,即其根结点是否相同;
方法是将有联系的村庄编号存为数组,将其距离存为对应值,找出不同根结点之间的最小距离,然后相加,得出需建的最短公路;
View Code
1 //杭电1233
2 //C++提交
3 #include<stdio.h>
4 #include<string.h>
5 #define Max 65535
6 int n;
7 int f[101][101],set[101];
8 void power()
9 {
10 int i,j,min=f[1][1],k=0,x=1,y=1,totle=0,temp;
11 while(k<n-1)
12 {
13
14 for(i=1;i<n;i++)//用循环找出两村庄之间的最短距离,并记下村庄编号i,j,
15 for(j=i+1;j<=n;j++)
16 {
17 if(min>f[i][j])
18 {
19 min=f[i][j];
20 x=i;
21 y=j;
22 }
23 }
24 if(set[x]!=set[y])//判断这两个村庄的根节点是否一致
25 {
26 k++;
27 totle+=min;//记下最短公路距离和
28 temp=set[y];
29 for(i=1;i<=n;i++)//找出与y村庄共根结点的编号
30 {
31 if(temp==set[i])
32 set[i]=set[x];//将这些共根结点的编号全部置为与x共根结点
33 }
34 }
35 min=f[x][y]=Max;//把已经记过的距离置为最大,避免下次重复
36 }
37 printf("%dn",totle);
38 }
39
40
41 int main()
42 {
43 int i,k;
44 int a,b,c;
45 while(scanf("%d",&n),n!=0)
46 {
47 for(i=1;i<=n;i++)
48 set[i]=i;
49 k=n*(n-1)/2;
50
51 for(i=1;i<=k;i++)
52 {
53 scanf("%d%d%d",&a,&b,&c);
54 f[a][b]=c;//把有联系的村庄存成数组,将其之间的距离赋值给数组
55 }
56 power();
57 }
58 return 0;
59 }
原文链接: https://www.cnblogs.com/zlyblog/archive/2012/07/17/2594825.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/55689
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!