P1111 修复公路 洛谷
2024-08-30 06:54:41
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 ;
}
最新文章
- mysql-front导出数据库字典
- Mysql运行SQL文件 错误Incorrect table definition;there can be only one TIMESTAMP column with CURRENT_TIMESTAMP in DEFAULT or ON UPDATE clause
- 模拟淘宝登录和购物车功能:使用cookie记录登录名,下次登录时能够记得上次的登录名,使用cookie模拟购物车功能,使用session记住登录信息并验证是否登录,防止利用url打开网站,并实现退出登录功能
- ACTIVITI 源码研究之命令模式执行
- hdu1250(Java)大数相加的问题
- mysql 连接问题----转载
- .NET MVC插件化开发(支持Script和css压缩)
- JAVA代码静态检测之PMD
- 全平台轻量级 Verilog 编译器 & 仿真环境
- 【JMeter】if语句中不能Failure=false解决办法
- Spring2.5整合Ibatis入门级开发实例
- google的Python风格规范
- jvm本地实战
- 学习笔记53—Wilcoxon检验和Mann-whitney检验的区别
- 我在大学毕业后学习Linux系统的心得经验
- KVM总结-KVM性能优化之内存优化
- WaitForSingleObject函数的使用
- 让apache支持htaccess文件
- 如何在service实现弹出对话框
- Zoom Me FAQ
热门文章
- 分享一个Delphi跨平台Http库的封装,一个Delphi跨平台TCP库的封装
- NLP.TM | GloVe模型及其Python实现
- initWithNibName:bundle awakeFromNib 区别
- js截屏
- windows使用文件服务器搭建Git服务器
- PAT 乙级 1005
- verilog behavioral modeling--sequential and parallel statements
- python 有4个数字1234,能组成多少个互不相同且无重复的三位数数字。
- Solr通过配DIH对数据库数据做索引
- SpringBoot 多线程