Algorithm - Problem - 修复公路

修复公路 洛谷 P1111

问题描述

AA 地区在地震过后,连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
给出 AA 地区的村庄数 NN ,和公路数 MM ,公路是双向的。并告诉你每条公路的连着哪两个村庄,并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车,即最早什么时候任意两条村庄都存在至少一条修复完成的道路(可以由多条公路连成一条道路)

输入

11 行两个正整数 N,MN, M
下面 MM 行,每行 33 个正整数 x,y,tx,y,t ,告诉你这条公路连着 x,yx,y 两个村庄,在时间 tt 时能修复完成这条公路。

输出

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

样例输入
1
2
3
4
5
4 4
1 2 6
1 3 4
1 4 5
4 2 3
样例输出
1
5

并查集/最小生成树

分析

显而易见的并查集/最小生成树,只不过求的不是边权和,而是最长边,直接上代码.

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <algorithm>
#define MAXM (100000+5)
#define MAXN (1000+5)
#define MAX(a,b) (((a)>(b))?(a):(b))

int ex[MAXM];
int ey[MAXM];
int ew[MAXM];
int es[MAXM]; // Sorted
int f[MAXN];
bool kruskal_cmp(int i, int j) { return ew[i] < ew[j]; }
int ffind(int i)
{
return (f[i] == i) ? i : (f[i] = ffind(f[i]));
}
bool fsame(int i, int j)
{
int fi = ffind(i);
int fj = ffind(j);
return fi == fj;
}
void funion(int i, int j)
{
int fi = ffind(i);
int fj = ffind(j);
if(fi == fj) return;
f[fi] = fj;
}
int main()
{
int n, m;
int t = 0;
int num = 0;
std::cin >> n >> m;
for(int i = 1; i <= n; i++)
{
f[i] = i;
}
for(int i = 1; i <= m; i++)
{
std::cin >> ex[i] >> ey[i] >> ew[i];
es[i] = i;
}
std::sort(es + 1, es + 1 + m, kruskal_cmp);
for(int i = 1; i <= m; i++)
{
int sx = ex[es[i]];
int sy = ey[es[i]];
int sw = ew[es[i]];
if(!fsame(sx, sy))
{
funion(sx, sy);
t = MAX(t, sw);
num++;
}
}
std::cout << ((num >= n - 1 ) ? t : (-1));
}