修复公路题解

全栈程序员-站长 • 2026年3月18日下午8:12 • 未分类 • 阅读 3

修复公路

题目

题目背景

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

题目描述

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

输入格式

第 $1$ 行两个正整数 $N$
下面 $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

说明/提示

$N \leq 1000, M \leq 100000$
$x \leq N, y \leq N, t \leq 100000$

原题链接

题解

思路

这道题知道的人很容易看出，其实就是最小生成树的改版。如果要连接所有的村庄，我们不难得出，至少要 $N - 1$ 条边，然后就可以推出了，因为最少只需 $N - 1$ 条边，所以比 $N - 1$ 多的边都是没有用的，那么我们只需要找到和最小且能联通所有村庄的 $N - 1$ 条边。

运用算法

$K r u s k a l$

代码

#include  
     #include  
     using namespace std; #define MAXN 1000 #define MAXM  int father[MAXN + 5];//记录父节点实现并查集 int sum = 0;//累加生成树的边数， 用来判断是否能构成 struct node{ 
    int a, b, n; }s[MAXM + 5];//存储每边的信息 int find (int x){ 
   //查找祖先 if (father[x] != x){ 
    father[x] = find (father[x]);//路径压缩 } return father[x];//以将父节点置为了根节点，直接返回 } int op (int x, int y, int n){ 
   //判断此边是否可以加入生成树 int a = find (x), b = find (y);//先分别查找两节点的祖先节点 if (a != b){ 
   //如果祖先不一样 sum ++;//记录生成树里多了一条边 father[a] = b;//并连接两个并查集 return n;//返回此边时间 } else{ 
   //如果加入生成树后会构成环 return -1;//返回-1，表示不能加入 } } bool cmp (node a, node b){ 
   //用来按照边的建好时间来排序边 //时间短的排前面 if (a.n > b.n){ 
    return 0; } else{ 
    return 1; } } int main(){ 
    int n, m; int ans; //输入数据 scanf ("%d %d", &n, &m); for (int i = 1; i <= m; i++){ 
    scanf ("%d %d %d", &s[i].a, &s[i].b, &s[i].n); } //初始化并查集与边的顺序 for (int i = 1; i <= n; i++){ 
    father[i] = i; } sort (s + 1, s + 1 + m, cmp); //依次插入边 for (int i = 1; i <= m && sum <= n - 1; i++){ 
    int x = op (s[i].a, s[i].b, s[i].n); if (x != -1){ 
    ans = x; } } //判断是否满足任意两个节点之间都能到达 if (sum < n - 1){ 
    printf ("-1"); return 0; } else{ 
    printf ("%d", ans); return 0; } }

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

修复公路题解

修复公路