字典序是什么毒瘤

题意就是,要求一个给定起点,字典序最小的欧拉回路(可能不存在),多组数据

首先,只要存在度数是奇数的点就不存在.
接下来,先将每个点连的边按标号递增排序.然后dfs求欧拉回路就好了.

时间复杂度$O(nlogn+m)$,lyd老师用网络流里面的当前弧优化来优化欧拉回路真的神啊!

/**********/
#define MAXN 51
#define MAXM 2011
std::vector<pll>g[MAXN];
ll begin[MAXN];
bool vis[MAXM];
ll deg[MAXN],s[MAXM],top;
void dfs(ll u)
{
    for(ll &i=begin[u];i<g[u].size();++i)
    {
        ll cur=g[u][i].first,v=g[u][i].second;
        if(!vis[cur])
        {
            vis[cur]=1;
            dfs(v);
            s[++top]=cur;
        }
    }
}
int main()
{
    while(1)
    {
        top=0;
        memset(begin,0,sizeof begin);memset(vis,0,sizeof vis);
        memset(deg,0,sizeof deg);
        ll x=read(),y=read(),start=min(x,y);
        if(!x&&!y)break;
        ll w=read();
        g[x].push_back(pll(w,y)),g[y].push_back(pll(w,x));
        while(1)
        {
            x=read(),y=read();
            if(!x&&!y)break;
            w=read();
            g[x].push_back(pll(w,y)),g[y].push_back(pll(w,x));
        }
        bool fail=0;
        for(ll i=1;i<MAXN;++i)
            if(g[i].size()&1u)fail=1;
            else std::sort(g[i].begin(),g[i].end());
        if(fail)puts("Round trip does not exist.");
        else
        {
            dfs(start);
            while(top)printf("%lld ",s[top--]);
            putchar('\n');
        }
        for(ll i=1;i<MAXN;++i)g[i].clear();
    }
    return 0;
}