P4038 [CERC 1995] John's Trip

题意：

给出一张无向图，要求从起点开始遍历一遍所有的边，最后再回到起点，题目要求输出任意一组方案。

起点是第一组

x

和

y

中较小的一个，

z

是边的编号。

解法：

欧拉路模板题，直接开一个数组记录一下就好了，几乎不用改变什么。代码里有一点注释。

大概步骤就是：先根据欧拉路的定义判断是否存在欧拉路，如果存在的话再求字典序最小的欧拉路，一定是以边

1

为起始的欧拉路，然后将每个结点的边按序号从大到小排序，从而保证 dfs 的时候得到的是字典序最小的欧拉路。

注意的点：

题目中有说过：“两个整数之间用一个空格隔开，行末无空格。”你不会真的天真的以为这句话是多余的吧，我一直以为所有的评测机都会过滤掉行末空格，但这题貌似不太行，在这里卡了一会。

code:

CPP

#include<bits/stdc++.h>
#define me(a) memset(a,0,sizeof(a))
#define N 3005
#define M 105
using namespace std;
bool vis[N];
int x,y,z,S,m,n,cnt,in[M],ans[N],mp[M][N];
void add(int x,int y,int z){
    mp[x][z]=y,mp[y][z]=x;//存图
    in[x]^=1,in[y]^=1;//其实这个就是判断奇偶性的
}
void dfs(int x){//正常跑
    for(int i=1;i<=m;i++) if(mp[x][i]&&!vis[i])
        vis[i]=1,dfs(mp[x][i]),ans[++cnt]=i;
}
int main(){
    while(1){
        scanf("%d%d",&x,&y);
        if(x==0&&y==0) break;
        scanf("%d",&z);
        me(in),me(ans),me(vis),me(mp);
        cnt=0,n=max(x,y),m=z,S=min(x,y),add(x,y,z);
        //S是起点，n是点数，m是边数
        while(1){
            scanf("%d%d",&x,&y);
            if(x==0&&y==0) break;
            scanf("%d",&z),add(x,y,z);
            n=max({n,x,y}),m=max(m,z);
        }
        bool pd=0;
        for(int i=1;i<=n;i++)
            if(in[i]){pd=1;break;}//欧拉路的特性
		if(pd){puts("Round trip does not exist.");continue;}//特判
		dfs(S);
		for(int i=cnt;i>=1;i--){
			printf("%d",ans[i]);
			putchar(i!=1?' ':'\n');//你不会真的以为这一行是多余的吧
		}
    }
	return 0;
}

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

文章操作

P4038 [CERC 1995] John's Trip

题意：

解法：

注意的点：

code:

相关推荐

评论

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