道路建设

链接：https://www.nowcoder.net/acm/contest/76/B
来源：牛客网

道路建设

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld

题目描述

随着如今社会的不断变化，交通问题也变得越来越重要，所以市长决定建设一些公路来方便各个城市之间的贸易和交易。虽然市长的想法很好，但是他也遇到了一般人也经常头疼的问题，那就是手头的经费有限……在规划过程中，设计师们已经预算出部分城市之间建设公路的经费需求。现在市长想知道，它能不能将他的m个城市在有限的经费内实现公路交通。如果可以的话，输出Yes，否则输出No（两个城市不一定要直接的公路相连，间接公路到达也可以。）

输入描述:

测试输入包含多条测试数据
每个测试数据的第1行分别给出可用的经费c(<1000000)，道路数目n(n<10000)，以及城市数目m(<100)。
接下来的n行给出建立公路的成本信息，每行给出三个整数，分别是相连的两个城市v1、v2(0<v1,v2<=m)以及建设公路所需的成本h(h<100)。

输出描述:

对每个测试用例，输出Yes或No。

示例1

输入

输出

Yes

示例2

输入

10 2 2
1 2 5
1 2 15

输出

Yes

备注:

两个城市之间可能存在多条线路

 1 #include <iostream>
 2 #include <cstring>
 3 #include <string>
 4 #include <algorithm>
 5 #include <queue>
 6 using namespace std;
 7 long long c;
 8 int n, m;
 9 struct node
10 {
11     int u, v;
12     long long w;
13     friend bool operator<(node a, node b)
14     {
15         return a.w > b.w;
16     }
17 }e[10005];
18 int par[105];
19 int rak[105];
20 priority_queue<node>q;
21 void init()
22 {
23     int i;
24     while (!q.empty()) q.pop();
25     for (i = 1; i <= n; i++)
26     {
27         par[i] = i;
28         rak[i] = 1;
29     }
30 }
31 int find(int x)
32 {
33     if (par[x] == x) return x;
34     else return par[x] = find(par[x]);
35 }
36 void unite(int xx, int yy)
37 {
38     int x = find(xx);
39     int y = find(yy);
40     if (x == y) return;
41     else
42     {
43         if (rak[x] < rak[y])
44         {
45             par[x] = y;
46         }
47         else
48         {
49             par[y] = x;
50             if (rak[x] == rak[y])
51             {
52                 rak[x]++;
53             }
54         }
55     }
56 }
57 int main()
58 {
59     while (cin >> c >> m >> n)
60     {
61         init();
62         int i;
63         for (i = 1; i <= m; i++)
64         {
65             cin >> e[i].u >> e[i].v >> e[i].w;
66             q.push(e[i]);
67         }
68         long long s = 0;
69         int k = 0;
70         while (!q.empty())
71         {
72             node x = q.top();
73             q.pop();
74             if (find(x.u) != find(x.v))
75             {
76                 unite(x.u, x.v);
77                 s += x.w;
78                 k++;
79             }
80             if (k == n - 1) break;
81         }
82         if (s <= c) cout << "Yes" << endl;
83         else cout << "No" << endl;
84     }
85     return 0;
86 }