island岛屿

题目描述

你将要游览一个有N个岛屿的公园。从每一个岛i出发,只建造一座桥。桥的长度以Li表示。公园内总共有N座桥。尽管每座桥由一个岛连到另一个岛,但每座桥均可以双向行走。同时,每一对这样的岛屿,都有一艘专用的往来两岛之间的渡船。 相对于乘船而言,你更喜欢步行。

你希望所经过的桥的总长度尽可能的长,但受到以下的限制。

  • 可以自行挑选一个岛开始游览。
  • 任何一个岛都不能游览一次以上。
  • 无论任何时间你都可以由你现在所在的岛S去另一个你从未到过的岛D。

由S到D可以有以下方法:

  • 步行:仅当两个岛之间有一座桥时才有可能。对于这种情况,桥的长度会累加到你步行的总距离;
  • 渡船:你可以选择这种方法,仅当没有任何桥和/或以前使用过的渡船的组合可以由S走到D(当检查是否可到达时,你应该考虑所有的路径,包括经过你曾游览过的那些岛)。

注意,你不必游览所有的岛,也可能无法走完所有的桥。

编写一个程序,给定N座桥以及它们的长度,按照上述的规则,计算你可以走过的桥的最大长度。

第一行包含N个整数,即公园内岛屿的数目。岛屿由1到N编号。 随后的N行每一行用来表示一个岛。第i 行由两个以单空格分隔的整数,表示由岛i筑的桥。第一个整数表示桥另一端的岛,第二个整数表示该桥的长度Li。你可以假设对于每座桥,其端点总是位于不同的岛上。

$2 \le N \le 1000000$
$1 \le L_i \le 100000000$

代码

从每个岛出发只建造一座桥,任何一个岛都不能游览一次以上
即求出森林中所有基环树的直径之和

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
88
89
90
91
92
93
94
95
//注意数组大小
inline void add(int f, int t, int c){
ne[++ cnt] = head[f], head[f] = cnt, to[cnt] = t, co[cnt] = c, ++ num[f];
}

inline void color(int node, int fa){
q[l = r = 1] = node;
while(l <= r){
now = q[l ++], col[now] = fa;
for(int i = head[now]; i; i = ne[i])
if(!col[To = to[i]]) q[++ r] = To;
}
}

//不经过环上的边的情况
//most数组存每棵树的最长路径
//dig数组存以i为根的子树中的叶节点至i的最长路径
inline void line(){
l = 1, r = 0;
for(int i = 1; i <= n; ++ i)
if(num[i] == 1) q[++ r] = i;
while(l <= r){
now = q[l ++];
for(int i = head[now]; i; i = ne[i])
if(num[To = to[i]] > 1){
chkmax(most[col[now]], dig[now] + dig[To] + co[i]);
chkmax(dig[To], dig[now] + co[i]);//注意这两条的顺序
if((-- num[To]) == 1) q[++ r] = To;
}
}
}

void circle(int st, int k){
tot = 0, now = st;
while(num[now] > 1){//终止死循环
num[now] = 1;
down[++ tot] = dig[now];//所以dis[1]=0
for(int i = head[now]; i; i = ne[i])
if(num[To = to[i]] > 1) {
now = To;
dis[tot + 1] = dis[tot] + co[i];
break;//理解这个break;
}
}//找到环上的所有节点并存储它们的dig值和离st的距离

if(tot == 2){
for(int i = head[now]; i; i = ne[i])
if((To = to[i]) == st) chkmax(dis[tot], co[i]);//注意它会比较两次
chkmax(most[k], dis[tot] + down[tot] + down[1]);
//注意down[i]和dig[i]的区别
//查了两小时...
return;
}//特判两个节点成环的情况

for(int i = head[now]; i; i = ne[i])
if((To = to[i]) == st) {
dis[tot + 1] = dis[tot] + co[i];
break;
}//找到没有计算的那条边

for(int i = 1; i < tot; ++ i)
down[tot + i] = down[i], dis[tot + i] = dis[tot + 1] + dis[i];
//把环拆开成链然后利用单调队列求两点间的最大距离

q[l = r = 1] = 1;
int TOT = (tot << 1) - 1;//a-b-c-a-b
for(int i = 2; i <= TOT; ++ i){
while(l <= r && i - q[l] >= tot) ++ l;//其实还蛮不好想的...
chkmax(most[k], down[q[l]] + down[i] + dis[i] - dis[q[l]]);
while(l <= r && down[i] - dis[i] >= down[q[r]] - dis[q[r]]) -- r;
//这里很好理解
q[++ r] = i;
}
}


int main(){
n = read();
for(int i = 1, x, c; i <= n; ++ i){
x = read(), c = read();
add(i, x, c), add(x, i, c);
}
for(int i = 1; i <= n; ++ i)
if(! col[i]) color(i, ++ t);
line();
for(int i = 1; i <= n; ++ i){
if(num[i] > 1 && !vis[col[i]]){
vis[col[i]] = 1;
circle(i, col[i]);
ans += most[col[i]];
}
}
printf("%lld", ans);
return 0;
}