题解：P13920 [PO Final 2024] 冰场之舞 / The Ice Puzzle

· · 题解

把从一个 X 滑到另一个 X 的过程看成一条有向边（由于这个过程是可逆的，也可以看成无向边）。题目就变成了：构造一条从 S 开始的欧拉路径 / 欧拉回路，使得每个点的入度均为奇数。如果把所有边加进去图不连通显然无解。

设最终欧拉路径（或欧拉回路）的边集为 G。G 初始为空。首先找到一棵以 S 为根的 dfs 生成树，对于生成树内的一条边 a-b，我们在 G 中加入 a\to b 和 b\to a 两条边，这样整张图就弱连通了。如果有奇数个点不合法（入度为偶数），我们就找一个奇环加进 G（具体而言，可以找一条覆盖了奇数个结点的返祖边）。这样不合法的点就只有偶数个了。如果不存在奇环，且有奇数个点不合法，那么就不存在满足条件的欧拉回路，R=1 时无解。

我们从叶子结点开始向上遍历整棵生成树，对于一个点 x 如果其不合法，我们就在 G 中加入 x\to fa_x 和 fa_x\to x。最终根结点以外的点都合法了。如果根结点不合法，那么此时肯定有 R=0，我们随便找到根结点的一个儿子 k（如果没有就无解），然后把 S\to k，k\to S，S\to k 三条边加进 G。

注意到最后一步之前所有点的入度都等于出度，所以必然有欧拉回路。最后一步则保证了存在一条从 S 开始，k 结束的欧拉路径。

最后我们直接跑欧拉路径 / 欧拉回路即可。序列长度不超过 2K+K+2K+3=5K+3，实际情况不可能跑满，所以肯定能过。总时间复杂度 O(nm)。

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e6;

int n,m,tot,TP,fa[Maxn+5],chk[Maxn+5]; string s[Maxn+5];
int dep[Maxn+5],siz[Maxn+5],dfn[Maxn+5],cur,sum;
int tx[Maxn+5],ty[Maxn+5];
vector<int> id[Maxn+5],v[Maxn+5];
vector<char> all;

inline void Work(int x,int y)
{
    if(tx[x]<tx[y]) all.push_back('v');
    if(tx[x]>tx[y]) all.push_back('^');
    if(ty[x]<ty[y]) all.push_back('>');
    if(ty[x]>ty[y]) all.push_back('<');
}
struct Graph
{
    int px[Maxn+5],st[Maxn+5],top;
    vector<int> v[Maxn+5];
    inline void dfs(int x)
    {
        for(int i=px[x];i<v[x].size();i=px[x])
            px[x]=i+1,dfs(v[x][i]);
        st[++top]=x;
    }
    inline void Solve()
    {
        dfs(1); reverse(st+1,st+top+1);
        For(i,2,top) Work(st[i-1],st[i]);
    }
} G;
inline void Add(int x,int y) {G.v[x].push_back(y);}

inline int Find(int x) {return (fa[x]==x)?x:fa[x]=Find(fa[x]);}
inline void dfs(int x,int f)
{
    if(x>1) Add(x,f),Add(f,x),chk[x]^=1,chk[f]^=1;
    fa[x]=f,dfn[x]=++cur,siz[x]=1,dep[x]=dep[f]+1;
    for(auto y:v[x]) if(!dfn[y]) dfs(y,x),siz[x]+=siz[y];
}
inline void dfs1(int x,int f)
{
    for(auto y:v[x]) if(dfn[x]>=dfn[y] && dfn[x]<dfn[y]+siz[y])
        if(sum && (dep[x]-dep[y])%2==0)
        {
            sum=0; for(int i=x;i!=y;i=fa[i])
                Add(i,fa[i]),chk[i]^=1;
            chk[y]^=1,Add(y,x);
        }
    for(auto y:v[x]) if(fa[y]==x) dfs1(y,x);
}
inline void dfs2(int x,int f)
{
    for(auto y:v[x]) if(fa[y]==x) dfs2(y,x);
    if(x>1 && chk[x]) {chk[x]^=1,chk[f]^=1,Add(x,f),Add(f,x);}
}

int main()
{
    cin>>n>>m>>TP;
    For(i,1,n) cin>>s[i],s[i]=' '+s[i];
    For(i,1,n) id[i].resize(m+2);
    For(i,1,n) For(j,1,m) if(s[i][j]=='S') id[i][j]=++tot;
    For(i,1,n) For(j,1,m) if(s[i][j]=='X') id[i][j]=++tot;
    For(i,1,n) For(j,1,m) if(s[i][j]!='.')
        {int p=id[i][j]; tx[p]=i,ty[p]=j;}
    For(i,1,n)
    {
        int pr=0; For(j,1,m) if(s[i][j]!='.')
        {
            if(pr) v[pr].push_back(id[i][j]),v[id[i][j]].push_back(pr);
            pr=id[i][j];
        }
    }
    For(j,1,m)
    {
        int pr=0; For(i,1,n) if(s[i][j]!='.')
        {
            if(pr) v[pr].push_back(id[i][j]),v[id[i][j]].push_back(pr);
            pr=id[i][j];
        }
    }
    For(i,1,tot) fa[i]=i;
    For(i,1,tot) for(auto j:v[i]) {int x=Find(i),y=Find(j); if(x!=y) fa[x]=y;}
    For(i,1,tot) if(Find(i)!=Find(1)) {cout<<-1<<endl; return 0;}
    For(i,1,tot) chk[i]=1;
    For(i,1,tot) fa[i]=0;
    dfs(1,0);
    For(i,1,tot) sum^=chk[i];
    if(sum) dfs1(1,0);
    if(sum && TP==1) {cout<<-1<<endl; return 0;}
    dfs2(1,0);
    for(auto i:v[1]) if(sum) {Add(1,i),Add(i,1),Add(1,i),sum=0;}
    if(sum) {cout<<-1<<endl; return 0;}
    G.Solve();
    cout<<all.size()<<endl;
    for(auto i:all) putchar(i); cout<<endl;
    return 0;
}