图里斯塔

Makab · 2025-11-05 19:16:08 · 题解

图里斯塔

题意

给定一个竞赛图，对每个点，求：从其出发的不经过重复点的最长路径，输出方案。

题解

先给一个玩出来的结论：

一个点的一个合法答案为：以其为根的 dfs 树的后序遍历的 reverse。

下证之。

考虑点 u 的答案。

答案上界

路径长度的上界为以 u 为根的 dfs 树的 size。

证明是平凡的。

因为从 u 不可达的点不会出现在 dfs 树上，而可达的点至多经过一次。

构造方案

下面证，“以 u 为根的 dfs 树的后序遍历的 reverse” 是合法构造：

先证明一个引理：

对于 dfs 树上任意一对无祖先关系的点，在原图上边的方向为从 dfn 大的点向 dfn 小的点。

考虑反证：

不妨设这两点为 u，v 且 dfn_u < dfn_v。

若此边的方向为 u \rightarrow v ，则在访问 u 后，v 会被 u 子树中某点访问（注意 v 不会早于 u 被访问，因为钦定了 dfn_u < dfn_v）。

即这两点在 dfs 树上有祖先关系，矛盾。

再考察 dfs 树的后续遍历 \left\{ a \right\}，对于任意 (a_i, a_{i + 1})，必然存在边 a_i \leftarrow a_{i + 1}。

证明：

考虑 a_i 要么是 a_{i + 1} 的儿子；要么 a_i 与 a_{i + 1} 无祖先关系，且 dfn_{a_i} < dfn_{a_{i + 1}}，有引理得存在边 a_i \leftarrow a_{i + 1}。

所以倒着输出即可。

实现

每次找编号最小的出边，bitset 优化找边，复杂度 \mathcal{O(\frac{n^3}{w})}。

码

#define rep(i, st, ed) for (int i = (st), _##i = (ed); i <= _##i; ++i)
#define per(i, st, ed) for (int i = (st), _##i = (ed); i >= _##i; --i)
using namespace std;

constexpr int N = 2e3 + 5;

int n;
int ans[N], len;
bitset<N> g[N], available;

void dfs(int u) {
    available.reset(u);
    for (int v; (v = (g[u] & available)._Find_first()) <= n; dfs(v));
    ans[++len] = u;
}

int main() {
    read(n);
    rep(i, 2, n) qep(j, 1, i) {
        int w; read(w);
        w ? g[j].set(i) : g[i].set(j);
    }
    rep(s, 1, n) {
        len = 0;
        available.set(); available.reset(0);
        dfs(s);
        printf("%d", len);
        per(i, len, 1) printf(" %d", ans[i]);
        puts("");
    }
    return 0;
}