https://www.luogu.org/problem/show?pid=1111

题目背景

A地区在地震过后,连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。

题目描述

给出A地区的村庄数N,和公路数M,公路是双向的。并告诉你每条公路的连着哪两个村庄,并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车,即最早什么时候任意两条村庄都存在至少一条修复完成的道路(可以由多条公路连成一条道路)

输入输出格式

输入格式:

第1行两个正整数N,M

下面M行,每行3个正整数x, y, t,告诉你这条公路连着x,y两个村庄,在时间t时能修复完成这条公路。


输出格式:

如果全部公路修复完毕仍然存在两个村庄无法通车,则输出-1,否则输出最早什么时候任意两个村庄能够通车。

输入输出样例

输入样例#1:

4 4
1 2 6
1 3 4
1 4 5
4 2 3
输出样例#1:

5

说明

N<=1000,M<=100000

x<=N,y<=N,t<=100000

#include <algorithm>
#include <iostream>
#include <cstdio> using namespace std; int n,m,tot,day,tot_fa,ans;
int fa[];
bool num[];
struct node
{
int x,y,t;
} w[]; bool cmp(node a,node b)
{
return a.t<b.t;
} int find(int x)
{
if(x!=fa[x])
return fa[x]=find(fa[x]);
return x;
} int main()
{
cin>>n>>m;
for(int i=;i<=n;i++) fa[i]=i;
for(int i=;i<=m;i++)
cin>>w[i].x>>w[i].y>>w[i].t;
sort(w+,w+m+,cmp);
for(int i=;i<=m;i++)
{
int fa_x=find(w[i].x),fa_y=find(w[i].y);
if(fa_x!=fa_y)
{
fa[fa_x]=fa_y;
day=max(day,w[i].t);
ans++;
}
if(ans==n-)
{
cout<<day;
return ;
}
}
cout<<-;
return ;
}

最新文章

  1. mysql-front导出数据库字典
  2. Mysql运行SQL文件 错误Incorrect table definition;there can be only one TIMESTAMP column with CURRENT_TIMESTAMP in DEFAULT or ON UPDATE clause
  3. 模拟淘宝登录和购物车功能:使用cookie记录登录名,下次登录时能够记得上次的登录名,使用cookie模拟购物车功能,使用session记住登录信息并验证是否登录,防止利用url打开网站,并实现退出登录功能
  4. ACTIVITI 源码研究之命令模式执行
  5. hdu1250(Java)大数相加的问题
  6. mysql 连接问题----转载
  7. .NET MVC插件化开发(支持Script和css压缩)
  8. JAVA代码静态检测之PMD
  9. 全平台轻量级 Verilog 编译器 & 仿真环境
  10. 【JMeter】if语句中不能Failure=false解决办法
  11. Spring2.5整合Ibatis入门级开发实例
  12. google的Python风格规范
  13. jvm本地实战
  14. 学习笔记53—Wilcoxon检验和Mann-whitney检验的区别
  15. 我在大学毕业后学习Linux系统的心得经验
  16. KVM总结-KVM性能优化之内存优化
  17. WaitForSingleObject函数的使用
  18. 让apache支持htaccess文件
  19. 如何在service实现弹出对话框
  20. Zoom Me FAQ

热门文章

  1. 分享一个Delphi跨平台Http库的封装,一个Delphi跨平台TCP库的封装
  2. NLP.TM | GloVe模型及其Python实现
  3. initWithNibName:bundle awakeFromNib 区别
  4. js截屏
  5. windows使用文件服务器搭建Git服务器
  6. PAT 乙级 1005
  7. verilog behavioral modeling--sequential and parallel statements
  8. python 有4个数字1234,能组成多少个互不相同且无重复的三位数数字。
  9. Solr通过配DIH对数据库数据做索引
  10. SpringBoot 多线程