嗯...

题目链接:https://www.luogu.org/problemnew/show/P1111

这道题的关键是读懂题:

首先根据题中的一些扎眼的字眼我们可以判断这是一道用最小生成树来做的题...

但是注意一个东西:施工时是同时性的!!!!

所以,施工时间应该是要施工的道路中所需时间的最大值...

换句话说,就是要求我们合并时最大的边权,我们只需用一个ans来维护就行

其次,如何判断是否存在“全部公路修复完毕仍然存在两个村庄无法通车”的情况,这就要用到了生成树的概念:

在一幅图中将所有n个点连接起来的n-1条边所形成的树

而num我们存储的即为边的数量,将它与n-1进行比较即可

思路:

在最小生成树的模板的基础上进行修改,在合并x点和y点的时候用num记录所修的道路数量,用ans记录边权的最大值,上面已经说过,边权最大值即为所需的时间...最后输出时将num与n-1进行比较

AC代码:

 #include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; int f[], ans;
int num; struct node{
int x, y, l;
} a[]; inline int cmp(node i, node j){
return i.l < j.l;
} inline int find(int x){
if(f[x] != x)
f[x] = find(f[x]);
return f[x];
} int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++)
f[i] = i;
for(int i = ; i <= m; i++){
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].l);
}
sort(a+, a+m+, cmp);
for(int i = ; i <= m; i++){
int r1 = find(a[i].x);
int r2 = find(a[i].y);
if(r1 != r2){
f[r1] = r2;
num++;//道路数量
ans = max(ans, a[i].l);//时间
}
}
if(num >= n - ) printf("%d", ans);
else printf("-1");
return ;
}

AC代码

最新文章

  1. Ubuntu使用MyEclipse闪退的解决办法
  2. CSS知识回顾--读《CSS 那些事儿》笔记
  3. iOS NSOperation 异步加载图片 封装NSOperation 代理更新
  4. [Cocos2d-x For WP8]矩形碰撞检测
  5. Java基础 —— DOM
  6. poj 2942 点的双连通分量
  7. jQuery监听键盘事件及相关操作使用
  8. excel中匹配数据
  9. WebGL 高级技术
  10. Win7-64位+Oracle11.2g+使用PLSQL_Developer 的解决办法
  11. CentOS 7 扩大/root分区
  12. 学以致用二十四-----shell脚本中的列表及space
  13. 在word中粘贴的图片为什么显示不完整
  14. 尚硅谷springboot学习20-web开发简介
  15. VUE 关于理解$nextTick()的问题
  16. Android教材 | 第三章 Android界面事件处理(二)—— 杰瑞教育原创教材试读
  17. 二分查找算法(Python版)
  18. Overriding managed version XX for YY
  19. 学习HTML 第二节.HTML头部
  20. [转译] AD RMS 安装最佳实践

热门文章

  1. Pagination分页
  2. 201671010140. 2016-2017-2 《Java程序设计》java学习第五周
  3. solrcloud使用问题记录
  4. std:: lower_bound std:: upper_bound
  5. 【NOI2002】荒岛野人
  6. 流Stream
  7. Linux mii-tool命令
  8. 1.scala基础语法总结
  9. Luogu 3265 [JLOI2015]装备购买
  10. 开源许可证GPL、BSD、MIT、Mozilla、Apache和LGPL的区别(转)