题解：P4038 [JSOI2010] 旅行

· · 题解

洛谷管理快修这题数据。

三倍经验：P4038，SP9528，UVA302。

一本通提高篇的题居然还能写题解。

这题甚至比板子简单。n\leq 44,m\leq 1995 是闹着玩的？

很明显就是在有向图里找一个字典序最小的欧拉回路，每次输入数据结束后，先用判断图是否满足欧拉回路的条件，满足的话跑一遍求欧拉回路的 DFS 即可，注意求的是字典序最小，要对于每个边的出度点排序，本题数据很小，不用当前弧优化。

过程是很平凡的，不会求的左转 P7771 【模板】欧拉路径，和这题一模一样。

注意格式！输出格式每组数据要额外换一行，和 LOJ 不一样！这题面和输入输出格式也太恶心了点。

代码：

#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=2001;
int n,m,u,v,w,s,d[N],ans[N],l;
bool vis[N],e;
vector<PII>G[N];
void dfs(int u){
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i].se,w=G[u][i].fi; 
        if(vis[w]) continue;
        vis[w]=1;
        dfs(v);
        ans[++l]=w;
    }
}
int main(){
    while(cin>>u>>v){
        if(!u&&!v){
            if(!e) break;
            for(int i=1;i<=2000;i++){
                sort(G[i].begin(),G[i].end());
                if(d[i]%2){
                    cout<<"Round trip does not exist.\n";
                    goto T2;
                }
            }
            dfs(s);
            while(l>1) cout<<ans[l--]<<" ";
            cout<<ans[l--]<<endl;
            T2:;
            memset(vis,0,sizeof vis);
            memset(d,0,sizeof d);
            for(int i=1;i<=2000;i++) G[i].clear();
            s=0;
            e=0;
            cout<<endl;
            continue;
        }
        e=1;
        cin>>w;
        if(!s) s=min(u,v);
        G[u].push_back({w,v});
        G[v].push_back({w,u});
        d[u]--;
        d[v]++;
    }
}