首页 > 代码库 > ACM 畅通工程2

ACM 畅通工程2

2024-11-21 06:23:39   203人阅读

Problem Description
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。
 

 

Input
测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N 
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。
 

 

Output
对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。
 

 

Sample Input
3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100
 

 

Sample Output
3
?
题解：统计数据不足以保证畅通--》没有生成最小生成树
　　　先把道路信息按照成本从小到大排列，然后用并查集生成最小树，得到所需的最小成本！
 1 /*
 2     Time: 2017/8/8
 3 */
 4 #include<stdio.h>
 5 #include<iostream>
 6 #include<algorithm>
 7 using namespace std;
 8 int parent[105];
 9 struct node{
10     int a,b,v;
11 }casei[999];
12 
13 //初始化parent数组 
14 void init()
15 {
16     for(int i = 0; i < 105;i++)
17         parent[i] = i; 
18 } 
19 
20 //找根节点
21 int find(int n)
22 {
23     if(parent[n] == n)
24         return n;
25     else
26         return find(parent[n]);
27  } 
28  
29  //
30 int merge(int a,int b)
31 {
32      a = find(a);
33      b = find(b);
34      if(a != b)
35      {
36          parent[b] = a;
37          return 1;    
38      }
39     else
40         return 0;
41     
42                 
43 }
44  
45  //
46  bool cmp(node a,node b)
47  {
48      return a.v < b.v;
49  }
50  
51 int main()
52 {
53     int n,m;
54     while(cin>>n>>m&&n!=0)
55     {
56         init();
57         for(int i = 0; i < n; i++)
58         {
59             cin>>casei[i].a>>casei[i].b>>casei[i].v;
60             
61         }
62         sort(casei,casei+n,cmp);
63         int sum = 0;
64         int count = 0;
65         int ans = 1;
66         for(int i = 0; i < n; i++)
67         {
68             int p = merge(casei[i].a,casei[i].b);
69             if(p)   
70             {
71                 sum += casei[i].v;
72             
73             }
74                 
75         }
76         for(int i = 1; i <= m;i++)
77         {
78             if(parent[i] == i) count++;
79             if(count > 1) 
80             {
81                 ans = 0;
82                 break;
83             }
84         }
85         
86         if(ans)  cout<<sum<<endl;
87         else  cout<<"?"<<endl;
88     }
89 
90 return 0;
91 }

 

ACM 畅通工程2


联系
我们