首页 > 代码库 > poj1041欧拉回路

poj1041欧拉回路

#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>#include <stack>#include <queue>#include <vector>#include <map>#include <string>#include <iostream>using namespace std;const int maxn=2000;int len;int head[maxn];struct Node{    int a;int b;int c;}node[maxn];struct edge{    int to;int val;int next;int op;int vis;}e[maxn*maxn];int add(int from,int to,int val){    e[len].to=to;    e[len].val=val;    e[len].next=head[from];    head[from]=len++;    return len-1;}int n=0;int sum;int cmp(const Node &a,const Node &b){    return a.c<b.c;}void dfs(int u){    for(int i=head[u];i!=-1;i=e[i].next){        if(!e[i].vis){            e[i].vis=1;e[e[i].op].vis=1;            int cc=e[i].to;            dfs(cc);            cout<<e[i].val<<" ";        }    }}int main(){    int a;int b;int c;    int degree[maxn];    while(scanf("%d%d",&a,&b),a||b){        memset(degree,0,sizeof(degree));        len=0;        memset(head,-1,sizeof(head));        sum=0;        scanf("%d",&c); node[sum].a=a;node[sum].b=b;node[sum].c=c;        sum++;if(a>n) n=a;if(b>n) b=n;        while(scanf("%d%d",&a,&b),a||b){            scanf("%d",&c);node[sum].a=a;node[sum].b=b;node[sum].c=c;            sum++;if(a>n) n=a;if(b>n) n=b;        }        sort(node,node+sum,cmp);        for(int i=0;i<sum;i++){            int a=node[i].a;int b=node[i].b;int c=node[i].c;            int cc=add(a,b,c);int cc1=add(b,a,c);            degree[a]++;degree[b]++;            e[cc].op=cc1;e[cc1].op=cc;            e[cc].vis=e[cc1].vis=0;        }        int flag=0;        for(int i=0;i<sum;i++){            int a=node[i].a;int b=node[i].b;            if((degree[a]&1)||(degree[b]&1)) {                flag=1;break;            }        }        if(!flag){            dfs(1);        }        else            cout<<"Round trip does not exist.";        cout<<endl;    }    return 0;}