CF36E-拓冰建站

这题有点哈人。
首先题意显然是欧拉路径。但是要求的是通过两条而不是一条路径覆盖全部边。
考虑分类讨论，连通块个数显然与答案相关。
首先特判一些显然错误的情况：

连通块个数多于 \(2\) 显然无法两条路径覆盖。
奇点个数多于 \(4\) 无法达成。
边数少于 \(2\) 无法达成。

接着我们考虑连通块个数为 \(1\) 时如何求答案。
当奇点个数为 \(0\) 或 \(2\) 时答案显然是正常求一条欧拉路径然后分割成两半。
由此我们可以思考两条路径是否也可以由一条分割成两条得到。
此时我们可以建一条虚边连接两个奇点，这样奇点个数就降为 \(2\)，可以正常跑欧拉路径。
而这样子实际上相当于合并了两个欧拉图，那最后根据这条新边分成两条路径即可。

再考虑连通块个数为 \(2\) 时如何处理。
若两个块各自奇点数不超过 \(2\)，则直接分别跑一遍欧拉回路即可。
若超过则无解。
实际实现起来还挺复杂的，要注意重边，四奇点等问题。
代码如下：

#include<bits/stdc++.h>
#define il inline
#define void il void
#define gc getchar
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define ll long long
#define pii pair<int,int>
#define fir first
#define sec second
#define e_b emplace_back
#define END {cout<<"-1\n";return;}
#define db cout<<1;
#define ooo mp[pii{stk[tp],stk[tp-1]}]
#define ttt mp[pii{stk[k],stk[k-1]}]
using namespace std;
const int N=2e4+5,mod=998244353,inf=1e9;
map<pii,int>mp;
vector<int>e[N];
int h[N];
int m,tu[N],n;
int cur[N],be[N];
bool vis[N],bb[N];
int ev[N],tot,stk[N],tp;
int rt[N];
vector<pii>g[N];
void dfs(int u){//cout<<u<<'\n';for(int i=cur[u];i<g[u].size();i=max(i+1,cur[u]))if(!vis[g[u][i].sec]){auto [v,id]=g[u][i];cur[u]=i+1;vis[id]=1,dfs(v);}stk[++tp]=u;
}
queue<int>q;
void bfs(int st){q.push(st),bb[st]=0;while(!q.empty()){int u=q.front();q.pop(),be[u]=st;for(auto [v,id]:g[u])if(bb[v])bb[v]=0,q.push(v);}
}
int ck(){int ct=0;for(int i=1;i<=n;i++)if(bb[i])bfs(i),rt[++ct]=i;return ct;
}
void solve(){cin>>m;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;g[u].e_b(pii{v,i}),g[v].e_b(pii{u,i});if(!mp.count(pii{u,v}))mp[pii{u,v}]=mp[pii{v,u}]=i;e[mp[pii{u,v}]].e_b(i);tu[u]++,tu[v]++,bb[u]=bb[v]=1;n=max(n,max(u,v));}if(m<2)END;for(int i=1;i<=n;i++)if(tu[i]&1)ev[++tot]=i;int num=ck();if(tot>4||tot==3||num>2)END;if(num==2){if(!tot){dfs(rt[1]);cout<<tp-1<<'\n';while(tp>1)cout<<e[ooo][h[ooo]++]<<' ',tp--;cout<<'\n';tp=0,dfs(rt[2]);cout<<tp-1<<'\n';while(tp>1)cout<<e[ooo][h[ooo]++]<<' ',tp--;}else if(tot==2){if(be[ev[1]]==rt[1]){dfs(ev[1]);cout<<tp-1<<'\n';while(tp>1)cout<<e[ooo][h[ooo]++]<<' ',tp--;cout<<'\n';tp=0;dfs(rt[2]);cout<<tp-1<<'\n';while(tp>1)cout<<e[ooo][h[ooo]++]<<' ',tp--;}else{//cout<<ev[1]<<' '<<ev[2]<<'\n';//cout<<rt[1]<<'\n';dfs(ev[1]);cout<<tp-1<<'\n';while(tp>1)cout<<e[ooo][h[ooo]++]<<' ',tp--;cout<<'\n';tp=0;dfs(rt[1]);cout<<tp-1<<'\n';while(tp>1)cout<<e[ooo][h[ooo]++]<<' ',tp--;}}else{if(be[ev[1]]==be[ev[2]]&&be[ev[3]]==be[ev[1]])END;if(be[ev[1]]==be[ev[2]])swap(ev[3],ev[2]);int u=ev[1],v=ev[2];g[u].e_b(pii{v,m+1}),g[v].e_b(pii{u,m+1});if(!mp.count(pii{u,v}))mp[pii{u,v}]=mp[pii{v,u}]=m+1;e[mp[pii{u,v}]].e_b(m+1);dfs(ev[3]);int k=tp;while(mp[pii{stk[k],stk[k-1]}]!=mp[pii{u,v}])k--;cout<<tp-k<<'\n';while(tp>k)cout<<e[ooo][h[ooo]++]<<' ',tp--;cout<<'\n';cout<<k-2<<'\n';k--;while(k>1)cout<<e[ttt][h[ttt]++]<<' ',k--;}}else{if(!tot){dfs(n);if(tp<2)END;cout<<tp-2<<'\n';while(tp>2)cout<<e[ooo][h[ooo]++]<<' ',tp--;cout<<'\n';cout<<1<<'\n'<<e[ooo][h[ooo]++]<<' ';}else if(tot==2){dfs(ev[1]);if(tp<2)END;cout<<tp-2<<'\n';while(tp>2)cout<<e[ooo][h[ooo]++]<<' ',tp--;cout<<'\n';cout<<1<<'\n'<<e[ooo][h[ooo]++]<<' ';}else{int u=ev[1],v=ev[2];g[u].e_b(pii{v,m+1}),g[v].e_b(pii{u,m+1});if(!mp.count(pii{u,v}))mp[pii{u,v}]=mp[pii{v,u}]=m+1;e[mp[pii{u,v}]].e_b(m+1);dfs(ev[3]);int k=tp;while(mp[pii{stk[k],stk[k-1]}]!=mp[pii{u,v}])k--;cout<<tp-k<<'\n';while(tp>k)cout<<e[ooo][h[ooo]++]<<' ',tp--;cout<<'\n';cout<<k-2<<'\n';k--;while(k>1)cout<<e[ttt][h[ttt]++]<<' ',k--;}}
}
int main(){//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;solve();
}