CF835F-Roads in the Kingdom
题目:
题目描述:
In the Kingdom K., there are $ n $ towns numbered with integers from $ 1 $ to $ n $ . The towns are connected by $ n $ bi-directional roads numbered with integers from $ 1 $ to $ n $ . The $ i $ -th road connects the towns $ u_{i} $ and $ v_{i} $ and its length is $ l_{i} $ . There is no more than one road between two towns. Also, there are no roads that connect the towns with itself.
Let’s call the inconvenience of the roads the maximum of the shortest distances between all pairs of towns.
Because of lack of money, it was decided to close down one of the roads so that after its removal it is still possible to reach any town from any other. You have to find the minimum possible inconvenience of the roads after closing down one of the roads.
输入格式:
The first line contains the integer $ n $ ( $ 3<=n<=2·10^{5} $ ) — the number of towns and roads.
The next $ n $ lines contain the roads description. The $ i $ -th from these lines contains three integers $ u_{i} $ , $ v_{i} $ , $ l_{i} $ ( $ 1<=u_{i},v_{i}<=n $ , $ 1<=l_{i}<=10^{9} $ ) — the numbers of towns connected by the $ i $ -th road and the length of the $ i $ -th road. No road connects a town to itself, no two roads connect the same towns.
It’s guaranteed that it’s always possible to close down one of the roads so that all the towns are still reachable from each other.
输出格式:
Print a single integer — the minimum possible inconvenience of the roads after the refusal from one of the roads.
样例:
样例输入 1:
1
2
3
4
| 3
1 2 4
2 3 5
1 3 1
|
样例输出 1:
样例输入 2:
1
2
3
4
5
6
| 5
2 3 7
3 1 9
4 1 8
3 5 4
4 5 5
|
样例输出 2:
思路:
实现:
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include "ybwhead/ios.h"
#define MAX (200000 + 7)
#define long long long
int N, M, c[MAX], use[MAX], head[MAX];
long ans1, ans2, FA, v[MAX], f[MAX], L[MAX], L0[MAX], R[MAX], R0[MAX];
struct edge
{
int y, z, nxt;
} E[MAX << 1];
void add(int x, int y, int z, int i)
{
E[i] = edge{y, z, head[x]};
head[x] = i;
}
#define y E[p].y
#define z E[p].z
int DFS(int x, int fa)
{
if (use[x])
return x;
use[x] = 1;
for (int p = head[x]; p; p = E[p].nxt)
if (y != fa)
{
FA = DFS(y, x);
if (FA)
{
c[++M] = x;
v[M] = z;
use[x] = 2;
return FA == x ? 0 : FA;
}
}
return 0;
}
void DFS2(int x, int fa)
{
for (int p = head[x]; p; p = E[p].nxt)
if (use[y] != 2 && y != fa)
{
DFS2(y, x);
ans1 = max(ans1, f[x] + f[y] + z);
f[x] = max(f[x], f[y] + z);
}
}
#undef y
#undef z
int main()
{
yin >> N;
for (int i = 1, x, y, z; i <= N; i++)
{
yin >> x >> y >> z;
add(x, y, z, i * 2);
add(y, x, z, i * 2 - 1);
}
DFS(1, -1); //找环，求解c，v数组。
for (int i = 1; i <= M; i++)
DFS2(c[i], 0), v[i] += v[i - 1]; //求解ans1，f数组并计算v的前缀和
//以上为树的直径知识
FA = L[0] = L0[0] = -1e18;
for (int i = 1; i <= M; i++)
{ //从左向右更新L和L0
L0[i] = max(L0[i - 1], f[c[i]] + v[i] + FA);
L[i] = max(L[i - 1], f[c[i]] + v[i]);
FA = max(FA, f[c[i]] - v[i]); //更新当前f[i]-c[i]最大值
}
FA = R[M + 1] = R0[M + 1] = -1e18;
for (int i = M; i >= 1; i--)
{ //同上
R0[i] = max(R0[i + 1], f[c[i]] - v[i] + FA);
R[i] = max(R[i + 1], f[c[i]] + v[M] - v[i]);
FA = max(FA, f[c[i]] + v[i]);
}
ans2 = 1e18;
for (int i = 1; i <= M; i++) //统计答案
ans2 = min(ans2, max(L[i - 1] + R[i], max(L0[i - 1], R0[i])));
yout << max(ans1, ans2) << endl;
}
|