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=,M=;

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=,int t=,int b=):nxt(n),to(t),bh(b) {}

}ed[M<<];

struct Tp{

  int x,y,bh;Tp(int x=,int y=,int b=):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]=;dfs(ed[i].to);

    p[++cnt]=ed[i].bh;

      }

}

int main()

{

  int x,y,z;

  while()

    {

      scanf("%d%d",&x,&y);if(!x&&!y)return ;

      st=min(x,y);n=max(x,y);m=;

      memset(hd,,sizeof hd);memset(vis,,sizeof vis);

      memset(deg,,sizeof deg);xnt=cnt=;flag=;

      scanf("%d",&z);tp[++m]=Tp(x,y,z);

      while()

    {

      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+,tp+m+);

      for(int i=;i<=m;i++)add(tp[i].x,tp[i].y,tp[i].bh);

      for(int i=;i<=n;i++)

    if(deg[i]&){flag=;break;}

      if(flag)printf("Round trip does not exist.\n");

      else

    {

      dfs(st);for(int i=cnt;i;i--)printf("%d ",p[i]);printf("\n");

    }

    }

}