题解：P3561 [POI 2017] Turysta

· · 题解

考虑缩点，由于是竞赛图所以缩点后一定是一条链。

先考察答案大小，我们猜测一个竞赛图中的 SCC 一定存在任意点出发的哈密顿路径，于是答案就是把点所在的 SCC 以及这个 SCC 在链上可以抵达的所有 SCC 大小加和。

构造答案等价于对每个点找其所在 SCC 中从其出发的哈密顿路径，为了好做，我们强化下问题，不妨对每个 SCC 直接构造哈密顿回路。

考虑建立 dfs 生成树构造，任选一个点建立 dfs 生成树，观察到树上横叉边一定是 dfs 序大的指向小的，且由于是竞赛图所有横叉边一定存在，于是考虑在 dfs 生成树上按照访问顺序的倒序合并一个点的所有子树的序列，再把这个点本身加入到序列开头，最后根处会得到从根出发的一条哈密顿路径。

但是我们想找的是一条回路，注意到找到的哈密顿路劲上最后一个点是 dfs 生成树上最左边的点（先访问的点放在左边），如果这个点存在到根的返祖边就最好，否则我们找到这个点的返祖边能回到的最浅的点，以这个点作为新根再次 dfs，优先遍历这个点到原先 dfs 生成树上最左边的点间的路径，得到的新 dfs 生成树再按照上面构造哈密顿路径的方法构造，得到的结果便是一条哈密顿回路。

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

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3+114;
bool E[maxn][maxn];
int n;
int dfn[maxn],low[maxn],dfncnt;
int col[maxn],cl,sz[maxn];
int vis[maxn],stk[maxn],tp;
bool e[maxn][maxn];
vector<int> seq[maxn];
int F[maxn];
void tarjan(int u){
    dfn[u]=low[u]=++dfncnt;
    stk[++tp]=u;
    vis[u]=1;
    for(int v=1;v<=n;v++){
        if(E[u][v]==1){
            if(dfn[v]==0){
                tarjan(v);
                low[u]=min(low[u],low[v]);
            }else if(vis[v]==1){
                low[u]=min(low[u],dfn[v]);
            }
        }
    }
    if(low[u]>=dfn[u]){
        cl++;
        F[cl]=u;
        while(stk[tp]!=u){
            col[stk[tp]]=cl;
            sz[cl]++;
            vis[stk[tp]]=0;
            tp--;
        }
        col[u]=cl;
        vis[u]=0;
        sz[cl]++;
        tp--;
    }
}
int dp[maxn],nxt[maxn];
int use[maxn];
int dep[maxn];
int g[maxn];
int root;
void dfs(int u,int now){
    use[u]=1;
    int d=0;
    for(int v=1;v<=n;v++){
        if(col[v]==now&&E[u][v]==1){
            if(use[v]==0){
                if(g[u]==0) g[u]=v;
                d++;
                dep[v]=dep[u]+1;
                dfs(v,now);
            }
        }
    }
    if(d==0&&root==0){
        for(int v=1;v<=n;v++){
            if(col[v]==now&&E[u][v]==1){
                if(root==0||dep[v]<dep[root]) root=v;
            }
        }
    }
}
vector<int> sol(int u,int now){
    use[u]=1;
    vector<int> res={u};
    vector< vector<int> > son;
    if(use[g[u]]==0&&g[u]!=0){
        son.push_back(sol(g[u],now));
    }   
    for(int v=1;v<=n;v++){
        if(col[v]==now&&E[u][v]==1&&use[v]==0&&v!=g[u]){
            son.push_back(sol(v,now));
        }
    }
    reverse(son.begin(),son.end());
    for(vector<int> x:son){
        for(int y:x) res.push_back(y);
    }
    return res;
}
void build(){
    int s=1;
    for(int i=2;i<=cl;i++){ 
        if(e[s][i]==1) s=i;
    }
    dp[s]=sz[s];
    for(int i=2;i<=cl;i++){
        int t=0;
        for(int j=1;j<=cl;j++){
            if(dp[j]==0){
                t=j;
            }
        }
        for(int j=1;j<=cl;j++){
            if(dp[j]==0){
                if(e[t][j]==1) t=j;
            }
        }
        dp[t]=sz[t]+dp[s];
        nxt[t]=s;
        s=t;
    }
    //构造哈密顿回路
    for(int i=1;i<=cl;i++){
        if(sz[i]!=1){
            root=0;
            dfs(F[i],i);
            memset(use,0,sizeof(use));
            seq[i]=sol(root,i);
        }else seq[i].push_back(F[i]);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            cin>>E[j][i];
            E[i][j]=E[j][i]^1;
        }
    }
    for(int i=1;i<=n;i++){
        if(dfn[i]==0) tarjan(i);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(col[i]!=col[j]) e[col[i]][col[j]]|=E[i][j];
    build();
    for(int i=1;i<=n;i++){
        cout<<dp[col[i]]<<" ";
        int t=0;
        for(int j=0;j<seq[col[i]].size();j++){
            if(seq[col[i]][j]==i) t=j;
        }
        for(int j=0;j<seq[col[i]].size();j++,t=(t+1)%seq[col[i]].size()) cout<<seq[col[i]][t]<<" ";
        int now=nxt[col[i]];
        while(now!=0){
            for(int x:seq[now]) cout<<x<<" ";
            now=nxt[now];
        }
        cout<<"\n";
    }
    return 0;
}