【poj1041】 John's trip

http://poj.org/problem?id=1041?(題目鏈接)

題意

　　給出一張無向圖，求字典序最小歐拉回路。

Solution

　　這鬼畜的輸入是什么心態啊mdzz，這里用vector儲存邊，便于邊的排序。瞬間變成STL常數boy →_→。

細節

　　數組大小把握好。

代碼

// poj1041
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;const int maxn=2000;
struct edge {int to,id;friend bool operator < (const edge a,const edge b) {return a.id<b.id;}
};
int vis[maxn],r[maxn],s[maxn],top,rt;
vector<edge> e[maxn];void dfs(int x) {for (int i=0;i<e[x].size();i++) if (!vis[e[x][i].id]) {vis[e[x][i].id]=1;dfs(e[x][i].to);s[++top]=e[x][i].id;}
}
int main() {int x,y,z;while (scanf("%d%d",&x,&y)!=EOF && x && y) {memset(vis,0,sizeof(vis));for (int i=1;i<maxn;i++) e[i].clear(),r[i]=0;rt=min(x,y);while (x && y) {scanf("%d",&z);e[x].push_back((edge){y,z});e[y].push_back((edge){x,z});r[x]++;r[y]++;scanf("%d%d",&x,&y);}int flag=0;for (int i=1;i<maxn;i++) if (r[i]&1) {flag=1;break;}if (flag) {puts("Round trip does not exist.");continue;}for (int i=1;i<maxn;i++) sort(e[i].begin(),e[i].end());top=0;dfs(rt);while (top) printf("%d ",s[top--]);puts("");}return 0;
}