只要弄懂欧拉回路的原理，即dfs找回路。
就能轻松的写出这题。
题目要求字典序最小。那么我们就无法让head[x]=i,加速找欧拉回路的过程。
老老实实的0(n*m)的算法遍历最小边权即可。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define ls (o<<1) #define rs (o<<1|1) #define pb push_back const double PI= acos(-1.0); const int M = 1e5+7; int head[M],cnt=1; struct EDGE{int to,nxt,w;}ee[M*2]; void add(int x,int y,int w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;} int st[M],sp[M],ans[M],vs[M],du[M]; void init() { cnt=1; memset(head,0,sizeof(head)); memset(vs,0,sizeof(vs)); memset(du,0,sizeof(du)); } int main() { ios::sync_with_stdio(false); cin.tie(0); int u,v,w; while(1) { init(); bool flag=false; int rt,n=0; while(cin>>u>>v) { if(u==0)break; if(!flag)rt=min(u,v);flag=true; cin>>w; add(u,v,w),add(v,u,w); n=max(n,max(u,v)); du[v]++,du[u]++; } if(cnt==1)break; flag=true; for(int i=1;i<=n;i++)if(du[i]==0||du[i]&1)flag=false; if(!flag) { cout<<"Round trip does not exist."<<endl; continue; } int top=0,t=0; st[++top]=rt; while(top) { int x=st[top],id=0,mi=1000000; for(int i=head[x];i;i=ee[i].nxt) { if(vs[i])continue; if(ee[i].w<mi)mi=ee[i].w,id=i; } // cout<<" - "<<x<<" "<<id<<" "<<ee[id].to<<endl; if(id) { int y=ee[id].to,w=ee[id].w; st[++top]=y; sp[top]=w; vs[id]=vs[id^1]=1; } else { //--top; ans[++t]=sp[top]; top--; } } int mi=1000000,id=0; for(int i=t-1;i;i--)cout<<ans[i]<<" "; cout<<endl; } return 0; }
