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

输入描述:

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

输出描述:

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

示例1

输入

复制

20 10 5
1 2 6
1 3 3
1 4 4
1 5 5
2 3 7
2 4 7
2 5 8
3 4 6
3 5 9
4 5 2

输出

复制

Yes

示例2

输入

复制

10 2 2
1 2 5
1 2 15

输出

复制

Yes

备注:

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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6 #include <utility>
 7 #include <vector>
 8 #include <map>
 9 #include <queue>
10 #include <stack>
11 #include <cstdlib>
12 #include <cmath>
13 typedef long long ll;
14 #define lowbit(x) (x&(-x))
15 #define ls l,m,rt<<1
16 #define rs m+1,r,rt<<1|1
17 using namespace std;
18 #define pi acos(-1)
19 #define P pair<ll,ll>
20 const int N  = 1e4+200;
21 int c,n,m;
22 int fa[N];
23 int u,v,w;
24 struct Edge{
25     int fr,to,val;
26     Edge(){}
27     Edge(int fr,int to,int val):fr(fr),to(to),val(val){}
28 }e[N*2];
29 bool cmp(Edge  a,Edge b)
30 {
31     return a.val<b.val;
32 }
33 void init()
34 {
35     for(int i =0;i<=m;i++) {
36         fa[i]=i;//=写成了== 
37     }
38 }
39 int find(int x)
40 {
41     return fa[x]=(x==fa[x]?x:find(fa[x]));
42 }
43 bool  prim()
44 {
45     sort(e,e+n,cmp);
46     int num=m,sum=0;//m:点的数目 ,错写成n了。 
47     for(int i =0;i<n;i++)
48     {
49         if(num>1){
50         int x=find(e[i].fr),y=find(e[i].to);
51         if(x!=y){
52             fa[x] = y;
53             num--;
54             sum+=e[i].val;
55         }        
56     }
57      }
58      if(num==1&&sum<=c){
59          return true;
60      } 
61      return false;
62 }
63 int  main()
64 {
65     while(~scanf("%d%d%d",&c,&n,&m)){
66         init();
67         for(int i =0;i<n;i++)
68         {
69             scanf("%d%d%d",&e[i].fr,&e[i].to,&e[i].val);
70         }
71         if(prim()){
72              printf("Yes\n");
73         }
74         else{
75             printf("No\n");
76         }
77     }
78     return 0; 
79 }