IOI2008 Island

发表于2020-07-15更新于2023-09-15字数统计1.4k阅读时长12分

Island

  • 题目链接
  • 图论/基环树/拓扑排序/树的直径
  • 数据结构/单调队列
  • 动态规划/环形DP/单调队列优化DP

Solution

基环树

NN 个点 NN 条边, 即在树上加一条边构成一个恰好包含一个环的图，称为基环树。若不保证联通，则可能是若干个基环树构成的森林，简称基环森林。求解基环数相关问题的方法一般是先找出图中的环，把除环之外的部分按照若干棵树处理，再考虑与环一起计算。

问题转换

根据题意，整个公园是一个基环树森林的形态。一旦离开一个基环树则不能再返回，因此答案就是各基环树的直径之和。

基环树直径

基环树直径(最长链)可能有两种情况:

  • 去掉环之后的某棵子树中，即求子树直径最大值
  • 经过环最长简单路径

求环可用拓扑排序，并在拓扑排序时 dpdp 求出某棵基环树去掉环的直径最大值 diameter[belong[node]]diameter[belong[node]]， 以及子树中以环上节点为起点的最长链 dis[nodeOnCircle]dis[nodeOnCircle]。
无向图进行拓扑排序， 节点入度为 1 则入队，拓扑排序后入度大于 1 则在环上。

拓扑排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline void topoSort() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (in[i] == 1) q.push(i);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto& e : G[cur]) {
            int to = e.first, w = e.second;
            if (in[to] > 1) {
                in[to]--;
                diameter[belong[to]] = max(diameter[belong[to]], dis[to] + dis[cur] + w);
                //dp求子树直径
                dis[to] = max(dis[to], dis[cur] + w);
                //dp求直径与以环结点为起点的子树中的最长链
                if (in[to] == 1) q.push(to);
            }
        }
    }
}

经过环的最长简单路径: 设环上有两节点为 Si,SjS_i,S_j，设它们在环上的最近距离为 cycleDis(Si,Sj)cycleDis(S_i,S_j)，则最长路径为 max⁡(dis[Si]+dis[Sj]+cycleDis(Si,Sj))\max(dis[S_i]+dis[S_j]+cycleDis(S_i,S_j))。把环断开成链再复制一倍，用单调队列即可 O(N)O(N) 解决。

单调队列
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
inline void dp(int cur, int cnt, LL res) {
    int st = cur, end = false, m(0);
    res = diameter[cnt];
    do {
        end = true, in[cur] = 1;
        tmpDis[++m] = dis[cur]; //根到节点的最长距离
        for (auto& e : G[cur]) {
            int to = e.first, w = e.second;
            if (in[to] <= 1) continue;
            end = false, cur = to;
            cycleDis[m + 1] = cycleDis[m] + w;
            break;
        }
    } while (!end);
    for (auto& e : G[cur]) { //回到起点
        int to = e.first, w = e.second;
        if (to == st) cycleDis[m + 1] = cycleDis[m] + w;
    }
    for (int i = 1; i < m; i++) {//断环成链 复制一倍
        tmpDis[i + m] = tmpDis[i]; //根到节点的最长距离
        cycleDis[i + m] = cycleDis[m + 1] + cycleDis[i]; //用于求出环上两节点距离
    }
    deque<int> q;
    q.push_back(1);
    for (int i = 2; i < 2 * m; i++) {
        while (!q.empty() && i - q.front() >= m) q.pop_front();
        res = max(res, tmpDis[i] + tmpDis[q.front()] + cycleDis[i] -
                           cycleDis[q.front()]);
        //让tmpDis[q.front()] + cycleDis[q.front()]单调递增
        while (!q.empty() &&
               tmpDis[i] - cycleDis[i] >= tmpDis[q.back()] - cycleDis[q.back()])
            q.pop_back(); //比当前值小则无效，直接弹出
        q.push_back(i);
    }
    ans += res;
}

Code

IOI Island
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
#include <bits/stdc++.h>
constexpr int MAXN = 1e6 + 6;
using namespace std;
using LL = long long;
using Arr = LL[MAXN];

LL n, ans;
Arr in, dis, diameter, belong, tmpDis, cycleDis;
vector<pair<int, int> > G[MAXN];

inline void bfs(int cur, int cnt) { //bfs处理出该节点属于哪一个基环树
    queue<int> q;
    q.push(cur);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        belong[cur] = cnt;
        for (auto& e : G[cur]) {
            int to = e.first;
            if (!belong[to]) q.push(to);
        }
    }
}

inline void topoSort() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (in[i] == 1) q.push(i);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto& e : G[cur]) {
            int to = e.first, w = e.second;
            if (in[to] > 1) {
                in[to]--;
                diameter[belong[to]] =
                    max(diameter[belong[to]], dis[to] + dis[cur] + w);
                dis[to] = max(dis[to], dis[cur] + w);
                //dp求直径与以环结点为起点的子树中的最长链
                if (in[to] == 1) q.push(to);
            }
        }
    }
}

inline void dp(int cur, int cnt, LL res) {
    int st = cur, end = false, m(0);
    res = diameter[cnt];
    do {
        end = true, in[cur] = 1;
        tmpDis[++m] = dis[cur]; //根到节点的最长距离
        for (auto& e : G[cur]) {
            int to = e.first, w = e.second;
            if (in[to] <= 1) continue;
            end = false, cur = to;
            cycleDis[m + 1] = cycleDis[m] + w;
            break;
        }
    } while (!end);
    for (auto& e : G[cur]) { //回到起点
        int to = e.first, w = e.second;
        if (to == st) cycleDis[m + 1] = cycleDis[m] + w;
    }
    for (int i = 1; i < m; i++) {//断环成链 复制一倍
        tmpDis[i + m] = tmpDis[i]; //根到节点的最长距离
        cycleDis[i + m] = cycleDis[m + 1] + cycleDis[i]; //用于求出环上两节点距离
    }
    deque<int> q;
    q.push_back(1);
    for (int i = 2; i < 2 * m; i++) {
        while (!q.empty() && i - q.front() >= m) q.pop_front();
        res = max(res, tmpDis[i] + tmpDis[q.front()] + cycleDis[i] -
                           cycleDis[q.front()]);
        //让tmpDis[q.front()] + cycleDis[q.front()]单调递增
        while (!q.empty() &&
               tmpDis[i] - cycleDis[i] >= tmpDis[q.back()] - cycleDis[q.back()])
            q.pop_back(); //比当前值小则无效，直接弹出
        q.push_back(i);
    }
    ans += res;
}

int main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int u = 1, v, w; u <= n; u++) {
        cin >> v >> w;
        G[u].emplace_back(make_pair(v, w));
        G[v].emplace_back(make_pair(u, w));
        in[u]++, in[v]++;
    }
    int cnt(0);
    for (int i = 1; i <= n; i++)
        if (!belong[i]) bfs(i, ++cnt);
    topoSort(); //拓扑排序求环
    for (int i = 1; i <= n; i++)
        if (in[i] > 1) dp(i, belong[i], 0);
    cout << ans << endl;
    return 0;
}