首页 > 代码库 > A - 还是畅通工程

A - 还是畅通工程

2024-11-19 00:21:04   203人阅读

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。 

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.

解题思路:最小生成树的问题,我使用的使Kruskal的算法

 1 #include <iostream>
 2 #include <queue>
 3 #include <string.h>
 4 #include <stdio.h>
 5 using namespace std;
 6 
 7 const int MAX = 100 + 20;
 8 int N;
 9 int visit[MAX];
10 
11 struct len
12 {
13     int a;
14     int b;
15     int len0;
16 };
17 
18 struct cmp
19 {
20     bool operator() ( len x,len y)
21     {
22         return x.len0 > y.len0;
23     }
24 };
25 
26 int Find(int x)
27 {
28     if(visit[x]==x)
29         return x;
30     else
31         return visit[x] = Find(visit[x]);
32 }
33 
34 int mix(int x,int y)
35 {
36     int TT = 0;
37     int Tx = Find(x);
38     int Ty = Find(y);
39     if(Tx!=Ty)
40     {
41         visit[Tx] = Ty;
42         TT = 1;
43     }
44     return TT;
45 
46 }
47 
48 int main()
49 {
50 
51     while(cin>>N)
52     {
53         if(N==0)
54             break;
55 
56         priority_queue<len,vector<len>,cmp>P;
57         for(int i = 1;i <=N;i++)
58             visit[i] = i;
59 
60         for(int i = 1;i <= N*(N-1)/2;i++ )
61         {
62             len temp;
63             scanf("%d %d %d",&temp.a,&temp.b,&temp.len0);
64             P.push(temp);
65         }
66 
67         int sum = 0;
68         for(int i = 1;i <=N*(N-1)/2;i++ )
69         {
70             len temp = P.top();
71             P.pop();
72 
73             if(mix(temp.a,temp.b)==1)
74             {
75                 sum += temp.len0;
76             }
77         }
78         cout<<sum<<endl;
79 
80     }
81 
82 
83     return 0;
84 }

 




A - 还是畅通工程


联系
我们