1. 全栈程序员必看首页

洛谷1111修复公路

全栈程序员-站长 • • 未分类 • 阅读 2

洛谷1111修复公路题目背景 A 地区在地震过后 连接所有村庄的公路都造成了损坏而无法通车 政府派人修复这些公路 题目描述给出 A 地区的村庄数 N 和公路数 M 公路是双向的 并告诉你每条公路的连着哪两个村庄 并告诉你什么时候能修完这条公路 问最早什么时候任意两个村庄能够通车 即最早什么时候任意两条村庄都存在至少一条修复完成的道路 可以由多条公路连成一条道路 输入输出格式输入格式 第 1 行两个正整数 N M 下面 M 行 每行 3 个正整

题目背景

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

题目描述

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

输入输出格式

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

输入输出样例

N<=1000，M<=

x<=N，y<=N，t<=

#include 
     #include 
     #include 
     using namespace std; const int maxM = (int)1e5; const int maxN = 1000; struct edge { int u, v, t; }G[maxM]; int operator <(edge x, edge y) { return x.t < y.t; } int pre[maxN + 1]; void getPre(int u) { if(pre[u] == u) return; getPre(pre[u]); pre[u] = pre[pre[u]]; } int main() { ios::sync_with_stdio(false); int n, m; cin >> n >> m; for(int i = 1; i <= n; i ++) pre[i] = i; for(int i = 0; i < m; i ++) cin >> G[i].u >> G[i].v >> G[i].t; int cnt = n; sort(G, G + m); for(int i = 0; i < m; i ++) { int u = G[i].u, v = G[i].v; getPre(u); getPre(v); if(pre[u] != pre[v]) { pre[pre[v]] = pre[u]; if(-- cnt == 1) { printf("%d", G[i].t); return 0; } } } printf("-1"); }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/225498.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月17日 上午9:11
下一篇 2026年3月17日 上午9:12


相关推荐

  • 单例模式singleton_单例模式详解

    单例模式singleton_单例模式详解

    单例模式singleton_单例模式详解单例模式 Singleton动机模式定义实例结构要点总结笔记动机在软件系统中，经常有一些特殊的类，必须保证它们在系统中只存在一个实例，才能保证他们的逻辑正确性、以及良好的效率如何绕过常规的构造器，提供一种机制来保证一个类只有一个实例？模式定义保证一个类仅有一个实例，并提供一个该实例的全局访问点。实例单例class Singleton{private : Singleton(); Singleton(const Singleton& other);public:

    全栈程序员-站长的头像 全栈程序员-站长
    2022年8月11日
    6
  • composer更新指定包||composer 常用命令「建议收藏」

    composer更新指定包||composer 常用命令「建议收藏」

    composer更新指定包||composer 常用命令

    全栈程序员-站长的头像 全栈程序员-站长
    2022年2月15日
    59
  • oracle11g数据库导入导出方法教程[通俗易懂]

    oracle11g数据库导入导出方法教程[通俗易懂]

    oracle11g数据库导入导出方法教程[通俗易懂]oracle11g数据库导入导出：①:传统方式——exp(导出)和(imp)导入：②:数据泵方式——expdp导出和（impdp）导入;③:第三方工具——PL/sqlDevelpoer;一、什么是数据库导入导出？oracle11g数据库的导入/导出，就是我们通常所说的oracle数据的还原/备份。数据库导入:把.dmp格式文件从本地导入到数据库服务器中(本地oracle测试数据库中…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年6月7日
    52
  • pytorch tensor操作：tensor与numpy转换

    pytorch tensor操作：tensor与numpy转换

    pytorch tensor操作：tensor与numpy转换tensor转numpyt=torch.ones(5)print(f”t:{t}”)n=t.numpy()print(f”n:{n}”)输出：t:tensor([1.,1.,1.,1.,1.],dtype=torch.float64)n:[2.2.2.2.2.]cpu上的tensor可以和numpyarray共享内存地址，改变其中的一个另一个也会改变t.add_(1)print(f”t:{t}”)print(f”n:{n}”)输出：t:

    全栈程序员-站长的头像 全栈程序员-站长
    2022年10月19日
    7
  • docker 导出镜像 docker

    docker 导出镜像

    docker 导出镜像导入导出命令介绍涉及的命令有 export import save loadsave 示例 dockersave onginx tarnginx latest 或 dockersave gt nginx tarnginx latest 其中 o 和 gt 表示输出到文件 nginx tar 为目标文件 nginx latest 是源镜像名 name tag 后面也可以是容器 idload 示例 dockerload inginx tar 或 dockerload

    全栈程序员-站长的头像 全栈程序员-站长
    2026年3月19日
    2
  • 都能看懂的LIS（最长上升子序列）问题[通俗易懂]

    都能看懂的LIS（最长上升子序列）问题[通俗易懂]

    都能看懂的LIS（最长上升子序列）问题[通俗易懂]LIS问题介绍：首先来说一下什么是LIS问题：有一个长为n的数列a0,a1,……,a(n-1)。请求出这个序列中最长的上升子序列的长度。上升子序列指的是对于任意的i<j都满足ai<aj的子序列，该问题被称为最长上升子序列（LIS，LongestIncreasingSubsequence）的著名问题。举个栗子：给你一个序列为（1，5，2，6，9，1…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年6月14日
    30

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号