2018年牛客多校算法寒假训练营练习比赛（第四场） 道路建设

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了2018年牛客多校算法寒假训练营练习比赛（第四场） 道路建设，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2429字，纯文字阅读大概需要4分钟。

内容图文

随着如今社会的不断变化，交通问题也变得越来越重要，所以市长决定建设一些公路来方便各个城市之间的贸易和交易。虽然市长的想法很好，但是他也遇到了一般人也经常头疼的问题，那就是手头的经费有限……在规划过程中，设计师们已经预算出部分城市之间建设公路的经费需求。现在市长想知道，它能不能将他的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 } 

 

内容总结

以上是互联网集市为您收集整理的2018年牛客多校算法寒假训练营练习比赛（第四场） 道路建设全部内容，希望文章能够帮你解决2018年牛客多校算法寒假训练营练习比赛（第四场） 道路建设所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---