P4381-[IOI2008]Island
题目:
题目描述:
你准备浏览一个公园，该公园由 $N$ 个岛屿组成，当地管理部门从每个岛屿 $i$ 出发向另外一个岛屿建了一座长度为 $L_i$ 的桥，不过桥是可以双向行走的。同时，每对岛屿之间都有一艘专用的往来两岛之间的渡船。相对于乘船而言，你更喜欢步行。你希望经过的桥的总长度尽可能长，但受到以下的限制：
- 可以自行挑选一个岛开始游览。
- 任何一个岛都不能游览一次以上。
- 无论任何时间，你都可以由当前所在的岛 $S$ 去另一个从未到过的岛 $D$。从 $S$ 到 $D$ 有如下方法：
- 步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离中。
- 渡船：你可以选择这种方法，仅当没有任何桥和以前使用过的渡船的组合可以由 $S$ 走到 $D$ (当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛)。
注意，你不必游览所有的岛，也可能无法走完所有的桥。
请你编写一个程序，给定 $N$ 座桥以及它们的长度，按照上述的规则，计算你可以走过的桥的长度之和的最大值。
输入格式:
第一行包含 $N$ 个整数，即公园内岛屿的数目。
随后的 $N$ 行每一行用来表示一个岛。第 $i$ 行由两个以单空格分隔的整数，表示由岛 $i$ 筑的桥。第一个整数表示桥另一端的岛，第二个整数表示该桥的长度 $L_i$。你可以假设对于每座桥，其端点总是位于不同的岛上。
输出格式:
仅包含一个整数，即可能的最大步行距离。
样例:
样例输入1:
1
2
3
4
5
6
7
8
| 7
3 8
7 2
4 2
1 4
1 9
3 4
2 3
|
样例输出1:
思路:
实现:
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
| #include "ybwhead/ios.h"
int n;
const int maxn = 1e6 + 10;
struct edge
{
int v, w, nxt;
} e[maxn << 1];
int tot, head[maxn];
void __ADD(int u, int v, int w)
{
e[++tot] = {v, w, head[u]};
head[u] = tot;
}
void add(int u, int v, int w)
{
__ADD(u, v, w);
__ADD(v, u, w);
}
bool v[maxn];
int v1[maxn];
long long ans;
int now, cnt;
int r[maxn];
int st;
long long s[maxn];
int dfs1(int u, int fa)
{
if (v1[u] == 1)
{
v1[u] = 2;
r[++cnt] = u;
v[u] = 1;
return 1;
}
v1[u] = 1;
// cout << u << endl;
for (int i = head[u]; i; i = e[i].nxt)
{
int vv = e[i].v;
if (i == ((fa - 1) ^ 1) + 1)
continue;
int tt = dfs1(vv, i);
if (tt == 0)
continue;
if (v1[u] == 2)
{
s[st - 1] = s[st] - e[i].w;
return 0;
}
r[++cnt] = u;
v[u] = 1;
s[cnt] = s[cnt - 1] + e[i].w;
return 1;
}
return 0;
}
long long ans1, ans2, ans3;
long long d[maxn];
void dp(int u)
{
v[u] = 1;
for (int i = head[u]; i; i = e[i].nxt)
{
int vv = e[i].v;
if (v[vv])
continue;
dp(vv);
ans1 = max(ans1, d[u] + d[vv] + e[i].w);
d[u] = max(d[u], d[vv] + e[i].w);
}
}
long long f[maxn << 1];
deque<int> q;
long long dfs(int u)
{
st = cnt + 1;
ans2 = ans3 = 0;
dfs1(u, 0);
for (int i = st; i <= cnt; i++)
{
ans1 = 0;
dp(r[i]);
ans2 = max(ans2, ans1);
f[i + cnt - st + 1] = f[i] = d[r[i]];
s[i + cnt - st + 1] = s[i + cnt - st] + s[i] - s[i - 1];
// yout << i << " " << s[4] << " " << s[3] << endl;
}
while (!q.empty())
q.pop_back();
// puts("!!!");
for (int i = st; i <= cnt * 2 - st + 1; i++)
{
while (!q.empty() && q.front() <= i - cnt + st - 1)
q.pop_front();
// yout << q.front() << " " << i - cnt + st - 1 << endl;
if (!q.empty())
ans3 = max(ans3, f[i] + f[q.front()] + s[i] - s[q.front()]);
while (!q.empty() && f[q.back()] - s[q.back()] <= f[i] - s[i])
q.pop_back();
q.push_back(i);
// yout << ans3 << endl;
}
return max(ans2, ans3);
}
int main()
{
yin >> n;
for (int i = 1; i <= n; i++)
{
int x, y;
yin >> x >> y;
add(i, x, y);
}
for (int i = 1; i <= n; i++)
if (!v[i])
ans += dfs(i);
yout << ans << endl;
return 0;
}
|