题意

给定一张 $n$ ($2\le n\le 2000$) 个点的竞赛图，找到从每个点开始的经过点数最多的简单路径。

题解

众所周知 $\ge 3$ 个点的强连通竞赛图有哈密顿回路，因此从 $u$ 开始最长的路径就是拓扑序在 $u$ 所属的强连通分量之后 (包括其本身) 的强连通分量的哈密顿路径相连。在每个强连通分量找到哈密顿回路即可。找哈密顿回路时，首先找到一条哈密顿路径 (按任意顺序加点即可)，然后找到路径上第一个向第一个点有边的点，作为初始的环。之后每次找到第一个向环中点有边的点，将它及之前未加入的点加入即可。

时间复杂度：$O(n^2)$。

代码

#include <iostream>
#include <vector>
#include <algorithm>
int n;
std::vector<std::vector<bool>> g;
int cntScc, dfsClock;
std::vector<int> dfn, low, belong;
std::vector<int> stk;
std::vector<std::vector<int>> ans;
std::vector<std::vector<int>> h;
void tarjan(int u) {
    dfn[u] = low[u] = dfsClock++;
    stk.push_back(u);
    for (int v = 0; v < n; ++v) {
        if (g[u][v]) {
            if (dfn[v] == -1) {
                tarjan(v);
                low[u] = std::min(low[u], low[v]);
            } else if (belong[v] == -1) {
                low[u] = std::min(low[u], dfn[v]);
            }
        }
    }
    if (dfn[u] == low[u]) {
        int v;
        do {
            v = stk.back();
            belong[v] = cntScc;
            stk.pop_back();
        } while (v != u);
        ++cntScc;
    }
}
auto solve(std::vector<int> v) {
    if (int(v.size()) == 1)
        return v;
    std::vector<int> h;
    for (auto u : v)
        h.insert(std::find_if(h.begin(), h.end(), [&](int v) {return g[u][v];}), u);
    auto it = std::find_if(h.begin(), h.end(), [&](int v) {return g[v][h[0]];}) + 1;
    std::vector<int> c(h.begin(), it);
    while (it != h.end()) {
        auto r = it;
        while (std::find_if(c.begin(), c.end(), [&](int v) {return g[*r][v];}) == c.end())
            ++r;
        auto p = c.begin();
        while (p + 1 != c.end() && !(g[*p][*it] && g[*r][*(p + 1)]))
            ++p;
        c.insert(p == c.end() ? c.begin() : p + 1, it, r + 1);
        it = r + 1;
    }
    return c;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n;
    g.assign(n, std::vector<bool>(n));
    dfn.assign(n, -1);
    low.resize(n);
    belong.assign(n, -1);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            int x;
            std::cin >> x;
            g[i][j] = x ^ 1;
            g[j][i] = x;
        }
    }
    for (int i = 0; i < n; ++i)
        if (dfn[i] == -1)
            tarjan(i);
    h.resize(cntScc);
    ans.resize(n);
    for (int i = 0; i < n; ++i)
        h[belong[i]].push_back(i);
    for (int i = 0; i < cntScc; ++i) {
        h[i] = solve(h[i]);
        for (auto it = h[i].begin(); it != h[i].end(); ++it) {
            int u = *it;
            ans[u].insert(ans[u].end(), it, h[i].end());
            ans[u].insert(ans[u].end(), h[i].begin(), it);
            for (int j = i - 1; j >= 0; --j)
                ans[u].insert(ans[u].end(), h[j].begin(), h[j].end());
        }
    }
    for (int i = 0; i < n; ++i) {
        std::cout << ans[i].size();
        for (int u : ans[i])
            std::cout << " " << u + 1;
        std::cout << "\n";
    }
    return 0;
}