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

题目链接: poj 1041

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

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

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

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

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

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

代码:

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