首页 > 代码库 > 修复公路
修复公路
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 41 2 61 3 41 4 54 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[1000015];bool num[1000015];struct node{ int x,y,t;} w[1000015];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=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) cin>>w[i].x>>w[i].y>>w[i].t; sort(w+1,w+m+1,cmp); for(int i=1;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-1) { cout<<day; return 0; } } cout<<-1; return 0;}
修复公路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。