Poj 1041 John's trip (Fleury算法求欧拉回路路径)

悠悠 2022-08-25 09:23 162阅读 0赞

题意：给出无向图，每条边有唯一的序号，是否存在欧拉回路，若存在输出边序号最小字典序的路径。

思路：Fleury算法求欧拉回路路径，Fleury算法其实就是DFS套了个人名……这里有个介绍http://blog.csdn.net/niushuai666/article/details/6549182

依据静态邻接表的特性，从序号大到小建立边，这样即可保证序号最小的边首先访问到

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    #define upmax(a,b) ((a)=(a)>(b)?(a):(b))
    
    const int N=2010;
    const int INF=0x3fffffff;
    
    int n,e,head[N];
    bool visit[N];
    int degree[N],id,answer[N];
    
    struct Node
    {
    	int v,way,pd,next;
    }edge[N<<3];
    
    struct Data
    {
    	int a,b,c;
    	bool operator < (const Data b) const
    	{
    		return c<b.c;
    	}
    }data[N<<3];
    
    void Add (int a,int b,int c)
    {
    	edge[e].v=b;
    	edge[e].way=c;
    	edge[e].next=head[a];
    	head[a]=e++;
    }
    
    void Fleury (int start)
    {
    	for (int i=head[start];i!=-1;i=edge[i].next)
    	{
    		int v=edge[i].v;
    		if (visit[edge[i].way]==false)
    		{
    			visit[edge[i].way]=true;
    			Fleury(v);
    			answer[++id]=edge[i].way;  //记录边的访问顺序,由于回溯,所以id越大越先访问
    		}
    	}
    }
    
    int main ()
    {
    	int i,limit=0,x,y,z;
    	while (scanf("%d%d",&x,&y),x||y)
    	{
    		int cnt=0;
    		e=id=0;
    		memset(visit,false,sizeof(visit));
    		memset(data,0,sizeof(data));
    		memset(head,-1,sizeof(head));
    		memset(degree,0,sizeof(degree));
    
    		scanf("%d",&z);
    		data[cnt].a=x,data[cnt].b=y,data[cnt++].c=z;
    		degree[x]++;
    		degree[y]++;
    		upmax(limit,x);
    		upmax(limit,y);
    		while (scanf("%d%d",&x,&y),x||y)
    		{
    			scanf("%d",&z);
    			upmax(limit,x);
    			upmax(limit,y);
    			degree[x]++;
    			degree[y]++;
    			data[cnt].a=x,data[cnt].b=y,data[cnt++].c=z;
    		}
    		bool flag=false;
    		for (i=1;i<=limit;i++)
    			if (degree[i]%2==1)   //有奇数度点则不存在欧拉回路
    			{
    				flag=true;
    				break;
    			}
    		if (flag)
    		{
    			printf("Round trip does not exist.\n");
    			continue;
    		}
    		sort(data,data+cnt);
    		for (i=cnt-1;i>=0;i--)
    		{
    			Add(data[i].a,data[i].b,data[i].c);
    			Add(data[i].b,data[i].a,data[i].c);
    		}
    		Fleury(1);
    		for (i=id;i>=1;i--)
    			printf(i==1?"%d\n":"%d ",answer[i]);
    	}
    	return 0;
    }