题解:P3561 [POI 2017] Turysta

· · 题解

P3561 [POI 2017] Turysta

给出一张 n 个节点的竞赛图,对于每个点 u 求出从 u 出发的最长简单路径。输出构造。

::::::success[题解]{open}

竞赛图找哈密顿回路练习题。

首先给出如下引理:

前两个定理在这篇 blog 讲的非常详细,这里不证。下面给出后两个定理的构造式证明:

::::success[Redéi 定理]

考虑增量构造。假设我们已经排好了 1 \sim k-1 的哈密顿路 u_1 \sim u_{k-1},尝试插入 k。找到一个位置 i 使得 (k,u_i), (u_{i+1},k) \in E,将 k 插入到 u_i,u_{i+1} 之间即可。注意特判放在首尾的情形。

::::

::::success[Camion-Moon 定理]

先用 Redéi 定理的构造找出一条哈密顿路,然后在路径上顺序扫描。

想象我们当前位于点 x,左侧已经被折叠成环 c_1 \to c_2 \to \cdots \to c_m \to c_1,右侧还是一条链,链是哈密顿路的一部分。

我们尝试将 x 插入环中。分类讨论:

::::

我们把这些定理应用到这个问题上。

利用 Landau 定理推论找出所有 SCC 并缩点后,DAG 的形态类似一条链。

考虑找出每个 SCC 的哈密顿回路。根据 DAG 的形态,直接取一段后缀的哈密顿回路拼起来,就能构成一条简单路径。

这样,这个问题的做法就显然了:利用 Camion-Moon 定理的构造求得 SCC 的哈密顿回路。对于一点 u,取拓扑序不小于其所在 SCC 的所有哈密顿回路拼起来。

精细实现复杂度 O(n^2),建议读者参照代码理解。

::::::

:::::info[代码]

const int N = 2005;
int n, m, d[N], p[N], bel[N];
vector<int> e[N], scc[N], hp[N];
bitset<N> has[N];

void work(int id) {
    vector<int> P, C;
    auto redei = [&]() -> void {
        for (int u : scc[id]) {
            int s = P.size();
            for (auto it = P.begin(); it != P.end(); it++) 
                if (has[u][*it]) {
                    P.insert(it, u); break;
                }
            if ((int)P.size() == s) P.emplace_back(u);
        }
    };
    auto camion = [&]() -> void {
        C.emplace_back(P[0]);
        int i = 1, n = P.size();
        while (i < n) {
            int c = C.size(), to = -1, u = P[i];
            for (int j = 0; j < c; j++) 
                if (has[u][C[j]]) {
                    to = j; break;
                }
            if (to != -1) {
                int p = 0;
                for (int j = 0; j < c; j++) {
                    int k = (j + 1) % c;
                    if (has[C[j]][u] && has[u][C[k]]) {
                        p = k; break;
                    }
                }
                if (p == 0) C.emplace_back(u);
                else C.insert(C.begin() + p, u);
                i++;
            } else {
                int j = i + 1, p = -1;
                for (; j < n && p == -1; j++) 
                    for (int k = 0; k < c; k++) 
                        if (has[P[j]][C[k]]) {
                            p = k; break;
                        }
                if (p == 0) C.insert(C.end(), P.begin() + i, P.begin() + j);
                else C.insert(C.begin() + p, P.begin() + i, P.begin() + j);
                i = j;
            }
        }
    };
    redei(), camion(), hp[id].swap(C);
}

void _main() {
    cin >> n;
    for (int u = 2; u <= n; u++) 
        for (int v = 1, x; v < u; v++) {
            cin >> x;
            if (x) e[v].emplace_back(u), has[v][u] = 1, d[u]++;
            else e[u].emplace_back(v), has[u][v] = 1, d[v]++;
        }
    iota(p + 1, p + n + 1, 1), sort(p + 1, p + n + 1, [](int u, int v) -> bool {
        return d[u] < d[v];
    });
    for (int i = 1, sum = 0, last = 0; i <= n; i++) {
        sum += d[p[i]];
        if (sum == i * (i - 1) / 2) {
            scc[++m] = vector<int>(p + last + 1, p + i + 1);
            for (int j = last + 1; j <= i; j++) bel[p[j]] = m;
            last = i;
        }
    }
    for (int i = 1; i <= m; i++) work(i);
    for (int u = 1; u <= n; u++) {
        vector<int> vec = hp[bel[u]];
        rotate(vec.begin(), find(vec.begin(), vec.end(), u), vec.end());
        for (int i = bel[u] + 1; i <= m; i++) 
            vec.insert(vec.end(), hp[i].begin(), hp[i].end());
        cout << vec.size() << ' ';
        for (int v : vec) cout << v << ' ';
        cout << '\n';
    }
} 

:::::