题解：P4038 [CERC 1995] John's Trip

· · 题解

题解：P4038 [CERC 1995] John's Trip

多测不清空，爆零两行泪！！

题意：

给定一张无向图，要求从起点（每组数据第一个边中的较小的编号）开始走过每一条边恰好一次，最后再回到起点，任意方案即可（本题解的方案满足字典序最小），无解输出 Round trip does not exist.。

思路：

欧拉回路模板题（模板题见：P7771【模板】欧拉路径），只不过将存储的内容改成了边的编号。

步骤：

  1. 判断是否存在欧拉回路：所有点的度都为偶数。
  2. 将每个点的边以边的编号为关键字排序。
  3. 跑一遍 Hierholzer，记得存储边的编号
  4. 输出答案

注意事项：

行末无空格。

输入较为恶心，注意细节。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3e3+111;
int n,m;
vector<pair<int,int> >g[N];
stack<int>ans;
int in[N];
int thi[N];
bool f[N];
void FC(int u){
    // for(int i=thi[u];i<int(g[u].size());i=thi[u]){
    //  thi[u]=i+1;
    for(int i=0;i<int(g[u].size());i++){
        int id=g[u][i].first;
        int v=g[u][i].second;
        if(f[id]){
            continue;
        }
        f[id]=1;
        FC(v);
        ans.push(id);
    }
}
int main(){
    while(1){
        for(int i=1;i<=N-11;i++){
            in[i]=0;
            thi[i]=0;
            f[i]=0;
            g[i].clear();
        }
        n=m=0;
        int topx=-1,topy=-1;
        while(1){
            int x,y,z;
            scanf("%d%d",&x,&y);
            if(x==0&&y==0){
                break;
            }
            if(topx==-1&&topy==-1){
                topx=x;
                topy=y;
            }
            n=max(n,max(x,y));
            m++;
            scanf("%d",&z);
            in[x]++;
            in[y]++;
            g[x].push_back(make_pair(z,y));
            g[y].push_back(make_pair(z,x));
        }
        if(m==0){
            break;
        }
        for(int i=1;i<=n;i++){
            sort(g[i].begin(),g[i].end());
        }
        int top=min(topx,topy);
        // int top=1;
        for(int i=1;i<=n;i++){
            if(in[i]%2==1){
                top=-1;
                break;
            }
        }
        if(top==-1){
            printf("Round trip does not exist.\n");
            continue;
        }
        FC(top);
        while(!ans.empty()){
            printf("%d",ans.top());
            ans.pop();
            if(ans.empty()){
                printf("\n");
            }else{
                printf(" ");
            }
        }
    }

    return 0;
}