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

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

题意：

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

思路：

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

步骤：

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

注意事项：

行末无空格。

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

代码：

CPP

#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;
}

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

文章操作

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

题意：

思路：

步骤：

注意事项：

代码：

相关推荐

评论

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