poj 1041 John's trip——欧拉回路字典序输出

题目：http://poj.org/problem?id=1041

明明是欧拉回路字典序输出的模板。

优先队列存边有毒。写跪。学习学习TJ发现只要按边权从大到小排序连边就能正常用邻接表了！

　　还有一种存边的方法是把边的标号放到数组第二维里，达到一个桶的效果。

我当然知道那种模板是先dfs再在return的时候把边加进栈里最后倒序输出，可是这题为什么不正序呢？

然后WA了。发现可能先把一个点的度走完但此时其他点还有度这样的。

于是有了flag和return。然后就超时了。

再看看TJ，突然就明白了为什么要用那个栈的模板。感觉理解更深刻了。

还是模板好呀！

get到了存边方法！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=50,M=2000;
int st,n,m,hd[N],xnt,p[M],cnt,deg[N];
bool vis[M],flag;
struct Ed{
  int nxt,to,bh;
  Ed(int n=0,int t=0,int b=0):nxt(n),to(t),bh(b) {}
}ed[M<<1];
struct Tp{
  int x,y,bh;Tp(int x=0,int y=0,int b=0):x(x),y(y),bh(b) {}
  bool operator< (const Tp &b)const
  {return bh>b.bh;}
}tp[M];
void add(int x,int y,int z)
{
  ed[++xnt]=Ed(hd[x],y,z);hd[x]=xnt;
  ed[++xnt]=Ed(hd[y],x,z);hd[y]=xnt;
  deg[x]++;deg[y]++;
}
/*
void dfs(int cr)
{
  if(cnt==m){flag=1;return;}
  for(int i=hd[cr];i;i=ed[i].nxt)
    if(!vis[ed[i].bh])
      {
    vis[ed[i].bh]=1;p[++cnt]=ed[i].bh;
    dfs(ed[i].to);
    if(flag)return;
    vis[ed[i].bh]=0;cnt--;
      }
}
*/
void dfs(int cr)
{
  for(int i=hd[cr];i;i=ed[i].nxt)
    if(!vis[ed[i].bh])
      {
    vis[ed[i].bh]=1;dfs(ed[i].to);
    p[++cnt]=ed[i].bh;
      }
}
int main()
{
  int x,y,z;
  while(1)
    {
      scanf("%d%d",&x,&y);if(!x&&!y)return 0;
      st=min(x,y);n=max(x,y);m=0;
      memset(hd,0,sizeof hd);memset(vis,0,sizeof vis);
      memset(deg,0,sizeof deg);xnt=cnt=0;flag=0;
      scanf("%d",&z);tp[++m]=Tp(x,y,z);
      while(1)
    {
      scanf("%d%d",&x,&y);if(!x&&!y)break;
      scanf("%d",&z);tp[++m]=Tp(x,y,z);
      n=max(n,(max(x,y)));
    }
      sort(tp+1,tp+m+1);
      for(int i=1;i<=m;i++)add(tp[i].x,tp[i].y,tp[i].bh);
      for(int i=1;i<=n;i++)
    if(deg[i]&1){flag=1;break;}
      if(flag)printf("Round trip does not exist.
");
      else
    {
      dfs(st);for(int i=cnt;i;i--)printf("%d ",p[i]);printf("
");
    }
    }
}