现在的位置: 首页 > 算法 > 正文

poj 1041 John’s trip (边最小字典序欧拉路径 Fleury)

2018年09月21日 算法 ⁄ 共 1617字 ⁄ 字号 评论关闭

题目链接:   poj 1041

题目大意:   给出无向图,每条边有唯一的序号

                  是否存在欧拉回路,若存在输出边序号最小字典序的路径

解题思路:   无向欧拉回路的判断方法,若存在奇数度点,则不存在欧拉回路

                  依据静态邻接链表的特性,从序号大到小建立边

                  因为这样总能保证序号最小的边首先访问到

                  PS:欧拉路径的问题要记得判断图是否联通

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX	2010
#define INF 0x3f3f3f3f
int S,E,n,Index,pre[MAX],visit[MAX],Du[MAX],kk,answer[MAX];
struct snode{
	int w,pd,to,next;
}edge[MAX<<3];
struct node{
	int a,b,c;
}ans[MAX<<3];

bool cmp(struct node a,struct node b)
{
	return (a.c<b.c)?1:0;
}

void Add_edge(int a,int b,int c)
{
	edge[Index].to=b;
	edge[Index].w=c;
	edge[Index].next=pre[a];
	pre[a]=Index++;
}

void Fleury(int start)
{
	int i,v;
	for(i=pre[start];i!=-1;i=edge[i].next)
	{
		v=edge[i].to;
		if(!visit[edge[i].w])
		{
			visit[edge[i].w]=1;
			Fleury(v);
			answer[++kk]=edge[i].w;  //记录边的访问顺序
		}
	}
}

int main()
{
	int i,k,a1,a2,a3,pd,start;
	while(scanf("%d%d",&a1,&a2)!=EOF)
	{
		k=1,Index=kk=pd=0;
		if(a1==0&&a2==0)
			break;
		memset(visit,0,sizeof(visit));
		memset(ans,0,sizeof(ans));
		memset(pre,-1,sizeof(pre));
		memset(Du,0,sizeof(Du));
		scanf("%d",&a3);
		ans[k].a=a1,ans[k].b=a2,ans[k].c=a3;
		Du[a1]++,Du[a2]++;
        if(a1>a2)
            S=a2,E=a1;
        else
            S=a1,E=a2;
		while(1)
		{
			scanf("%d%d",&a1,&a2);
			if(a1==0&&a2==0)
				break;
			scanf("%d",&a3);
			if(a1<S) S=a1;if(a2<S) S=a2;
			if(a1>E) E=a1;if(a2>E) E=a2;
			Du[a1]++,Du[a2]++;
			ans[++k].a=a1,ans[k].b=a2,ans[k].c=a3;
		}
		start=S;
		for(i=S;i<=E;i++)
		{
			if(Du[i]==0)
				continue;
			if(Du[i]%2==1)   //有奇数度点则不存在欧拉回路
			{
				pd=1;break;
			}
		}
		if(pd==1)
		{
			printf("Round trip does not exist.\n");
			continue;
		}
        sort(ans+1,ans+1+k,cmp);
		for(i=k;i>=1;i--)
		{
			Add_edge(ans[i].a,ans[i].b,ans[i].c);
			Add_edge(ans[i].b,ans[i].a,ans[i].c);
		}
		Fleury(start);
		for(i=kk;i>=1;i--)
			printf("%d%c",answer[i],(i==1)?'\n':' ');
	}
	return 0;
}

抱歉!评论已关闭.