题解：P3561 [POI 2017] Turysta

hjxhjx · 2025-03-22 10:50:20 · 题解

好像大家都是利用竞赛图的神奇性质做的，这里给出一个适合我这种无脑选手的做法。

首先对于每个出发点 S，以 S 为根搜出一棵 dfs 树。答案路径的长度显然不能超过这棵树的大小。

然后我们观察树上的一个分叉（根节点为 1，图上忽略了非树边）：

dfs 的顺序是：1→2→4→3→5。

因为这是个竞赛图，所以我们知道 2 和 5 之间的非树边一定是 5→2，否则 5 应该是 2 的儿子。

换句话说，给 dfs 遍历到的点赋一个时间戳，对于 dfs 树上任意两个没有祖先关系的点，他们之间的边一定是从时间戳大的指向时间戳小的。

那么做法也就呼之欲出了：每次走时间戳最大的儿子，需要回溯时就通过非树边一步跳到需要到的点，答案路径长度等于 dfs 树大小。

对于上图，答案路径就是 1→3→5→2→4。容易发现这其实是翻转的后序遍历。

直接做的复杂度是 O(n^3)，使用 bitset 优化可以做到 O(\frac{n^3}{w})，可以通过本题。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

inline static int read(){
    int sum=0,neg=0,ch=getchar();
    while(!isdigit(ch)) neg|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) sum=sum*10+(ch^48),ch=getchar();
    return neg?-sum:sum;
}

int n,L,arr[2005],l;
struct Bit{
    ull a[32];
    ull&operator[](int x){return a[x];}
    void flip(int x){a[x>>6]^=1ull<<(x&63);}
    int operator&(Bit&b){
        for(int i=0;i<=L;i++) if(a[i]&b[i])
            return __builtin_ctzll(a[i]&b[i])|i<<6;
        return 0;
    }
}e[2005],vis;
void dfs(int u,int v=0){
    for(vis.flip(u);(v=e[u]&vis);) dfs(v);
    arr[++l]=u;
}
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    n=read(),L=n>>6;
    for(int i=2;i<=n;i++) for(int j=1;j<i;j++)
        if(read()) e[j].flip(i); else e[i].flip(j);
    for(int i=1;i<=n;putchar('\n'),l=0,i++){
        memset(&vis,0xff,8*L+8),dfs(i),printf("%d ",l);
        for(int j=l;j>=1;j--) printf("%d ",arr[j]);
    } return 0;
}