POJ 1041 John's trip(欧拉回路+输出路径)
http://poj.org/problem?id=1041
题意:给你一个无向图,数据格式如点x 点y 边Z,表示由x点和y点构成了Z边。现在要问你该图中是否存在欧拉回路,如果存在,则输出字典序最小的那条欧拉回路(输入按序走过的所有边标号)。且题目中保证了该无向图是连通的。
分析:首先欧拉路径的输出方式可以参考刘汝佳入门经典P112中的代码。不过那里的图中的边是用(i,j)来表示的,而这里的图中的边是用一个数字编号表示的.所以源代码中还需要做点小修改.
然后要保证从John的家作为起始点输出欧拉回路且保证字典序最小,因为euler这个函数输出的欧拉路径是从起点逆序的(即起点被放到了最后才输出),所以我们需要把最后结果保存在ans数组中,最后逆序输出,且每次都是从小到大选择与当前节点相连的可行边的(这样可以保证输出结果的字典序最小).
当然还需要在用euler之前判断无向连通图的所有节点是不是都是偶数度,如果不是则不存在欧拉回路.
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxe=1995+10;
const int maxv=44+10;
struct edge
{
int u,v;
}edges[maxe];
int n,m;//n表示节点数,m表示边数,边与点都从1开始编号
int degree[maxv];//每个点的度数
int vis[maxe];//标记边是否被走过
int ans[maxe];//最终结果存在这里
int cnt;//当前存在ans中的边下标
bool ok()
{
for(int i=1;i<=n;i++)if(degree[i]%2!=0) return false;
return true;
}
void euler(int s)
{
for(int i=1;i<=m;i++)if(!vis[i] && (edges[i].u==s||edges[i].v==s) )
{
vis[i]=1;
euler(edges[i].u+edges[i].v-s);
ans[cnt++]=i;
}
}
int main()
{
int x,y,z;
while(scanf("%d%d",&x,&y)==2&&x)
{
cnt=n=m=0;
int John_home = min(x,y);
memset(degree,0,sizeof(degree));
memset(vis,0,sizeof(vis));
do
{
scanf("%d",&z);
edges[z].u=x;
edges[z].v=y;
degree[x]++;
degree[y]++;
m++;
n=max(n,max(x,y));
}while(scanf("%d%d",&x,&y)==2&&x);
if(!ok())
{
printf("Round trip does not exist.\n");
continue;
}
euler(John_home);
printf("%d",ans[m-1]);
for(int i=m-2;i>=0;i--)
printf(" %d",ans[i]);
printf("\n");
}
return 0;
}
分享到:
相关推荐
Catenyms poj hoj 欧拉回路输出路径
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
1.把自己的污水排到河里V 2.把自己的污水送到右边> 3.把自己的污水送到左边
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ初级题-数据结构:解题报告+AC代码
北大POJ2187-Beauty Contest 解题报告+AC代码
博客链接 http://blog.csdn.net/CABI_ZGX/article/details/52701138
北大POJ3252-Round Numbers 解题报告+AC代码
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1416-Shredding Company 解题报告+AC代码
北大POJ1019-Number Sequence 解题报告+AC代码
北大POJ3126-Prime Path 解题报告+AC代码
北大POJ1472-Instant Complexity 解题报告+AC代码
北大POJ1018-Communication System 解题报告+AC代码
北大POJ2531-Network Saboteur 解题报告+AC代码