現(xiàn)有一群設(shè)計(jì)師要在n（0<n<=100)個(gè) 城之間建立通信網(wǎng)絡(luò)，每兩個(gè)城市之間建設(shè)通信的線路費(fèi)用和城市的數(shù)目是已知的，現(xiàn)在他要你幫他找出建設(shè)網(wǎng)絡(luò)要花費(fèi)的最小的費(fèi)用，注意：網(wǎng)絡(luò)必須連接到所有的城市
輸入要求：輸入的包括多組數(shù)據(jù)，每組測試數(shù)據(jù)的第一行是城市的個(gè)數(shù)N，，然后每一行包括三個(gè)數(shù)據(jù)分別是
兩個(gè)城市和他們之間的距離，每組測試數(shù)據(jù)以三個(gè)0結(jié)束，
輸出要求：
對于每組數(shù)據(jù)，輸出建設(shè)通信網(wǎng)絡(luò)的最小花費(fèi)，每個(gè)測試實(shí)例占一行。
[樣例輸入]
6
1 2 6
1 3 1
1 4 5
2 3 5
2 5 6
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
0 0 0
樣例輸出：
8
代碼樣例
1 #include<stdio.h>
2 #include<string.h>
3 #include <algorithm>
4 using namespace std;
5 #define N 50
6 int V;
7 typedef struct Set
8 {
9 int data;
10 int tag;
11 }S;//tag是父節(jié)點(diǎn)
12 typedef struct {
13 int vs;//起始點(diǎn)
14 int ve;
15 int weight;
16 }Edge;
17 Edge e[N];
18 int find(S set[],int i)
19 {
20 while(set[i].tag>=0)
21 i=set[i].tag;
22 return i;
23 }
24 void uniol(S set[],int i,int j)
25 {
26 int sum;
27 i=find(set,i);
28 j=find(set,j);
29 if(i!=j)
30 {
31 sum=set[i].tag+set[j].tag;
32 set[j].tag=i;
33 set[i].tag=sum;
34 }
35 }
36 int Kruskal(S set[],Edge e[],int n)
37 {
38 int i,t=0,r1,r2,sum=0;
39 for(i=0;i<n;i++)
40 {
41 r1=find(set,e[i].vs);
42 r2=find(set,e[i].ve);
43 if(t==V-1)
44 break;
45 if(r1!=r2)
46 {
47 sum=sum+e[i].weight;
48 uniol(set,r1,r2);
49 t++;
50 }
51 }
52 return sum;
53 }
54
55 void sort(Edge e[],int n)
56 {
57 int i,j;
58 int t;
59
60 for(i=0;i<n;i++)
61 for(j=0;j<n-i-1;j++)
62 if(e[j].weight>e[j+1].weight)
63 {
64 t=e[j+1].weight;
65 e[j+1].weight=e[j].weight;
66 e[j].weight=t;
67 }
68 }
69
70 int main()
71 {
72 //freopen("123.txt","r",stdin);
73 int i,E,min_sum;
74 int s,e,w;
75 min_sum=0;E=0;//表示有多少條邊
76 S set[N];
77 Edge ed[N];
78 scanf("%d",&V);
79 for(i=0;i<N;i++)
80 {
81 set[i].data=i;
82 set[i].tag=-1;
83 }
84 while(scanf("%d%d%d",&s,&e,&w))
85 {
86 if(s==0&&e==0&&w==0)
87 break;
88 else{
89 ed[E].vs=s;
90 ed[E].ve=e;
91 ed[E].weight=w;
92 ++E;
93 }
94 }
95 sort(ed,E);
96 min_sum=Kruskal(set,ed,E);
97 printf("%d\n",min_sum);
98
99 return 0;
100
101
102 }
103
104
105 posted on 2012-07-20 15:59
天YU地___PS，代碼人生 閱讀(186)
評論(0) 編輯 收藏