## [$POJ$ $1041$ $John's$ $trip$](http://poj.org/problem?id=1041) ### 一、题目大意 多组数据,输入$x,y,z$,表示结点$x$和结点$y$之间有一条序号为$z$的边,如果这个 **无向图** 中存在欧拉回路,就 **输出字典序最小的欧拉回路**,如果不存在欧拉回路就输出 `Round trip does not exist. `。当输入`0 0`表示一组数据输入结束,题目保证了图的连通性。 给出一张无向图,要求从起点开始遍历一遍所有的边,最后再回到起点,题目要求输出任意一组方案 #### 细节 - 起点不是点$1$,而是第一条边中两个端点中较小的一个点 - 给出的$x$ $y$ $z$代表的是点$x$到点$y$由$id$为$z$的边连接 - 最后答案要求输出的是边的$id$ ### 二、解题思路 #### 欧拉回路 对于一个图可以从一个顶点沿着边走下去,每个边只走一次,所有的边都经过后回到原点的路。 #### 欧拉回路判定 - 无向图存在欧拉回路 $\Leftrightarrow$ 每个顶点的度是偶数 - 有向图存在欧拉回路 $\Leftrightarrow$ 每个顶点的出度等于入度(就是出去的边数等于进来的边数) #### 解题步骤 先根据欧拉路的定义判断是否存在欧拉路,如果存在的话再 **求字典序最小的欧拉路**,一定是以边$1$为起始的欧拉路,然后将每个结点的边按序号从大到小排序,从而保证$dfs$的时候得到的是字典序最小的欧拉路。 > **解释**:链式前向星是与$dfs$配合的,栈的原理,由大到小排序,最后走的就是小的,反着打出来就是由小到大 ### 三、$do \ while$版本 ```cpp {.line-numbers} #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int N = 2010, M = N * N; // 声明结构体 struct Node { int a, b, c; bool const operator<(const Node &t) const { return c > t.c; } } g[N]; int st[M]; // 某条边是不是访问过,无向图一般用于处理成对就换的边 int d[N]; // 度 int res[M], rl; // 路径数组 int m; // m条边 // 链式前向星 int e[M], h[N], idx, w[M], ne[M]; void add(int a, int b, int c = 0) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; } void dfs(int u) { for (int i = h[u]; ~i; i = h[u]) { // 删边优化 h[u] = ne[i]; if (st[i]) continue; st[i] = st[i ^ 1] = 1; // 成对变换 dfs(e[i]); // 记录路径 res[++rl] = w[i]; } } int main() { #ifndef ONLINE_JUDGE freopen("POJ1041.in", "r", stdin); #endif int a, b, c; while (true) { memset(d, 0, sizeof d); memset(st, 0, sizeof st); memset(h, -1, sizeof h); memset(res, 0, sizeof res); idx = rl = m = 0; // 本题的输入挺奇怪的,需要使用while(true)+do while的方式来读取最方便 scanf("%d%d", &a, &b); if (a == 0 && b == 0) exit(0); do { scanf("%d", &c); g[m].a = a, g[m].b = b, g[m++].c = c; scanf("%d%d", &a, &b); } while (a && b); // 针对边的边号进行由小到大排序 sort(g, g + m); for (int i = 0; i < m; i++) { int a = g[i].a, b = g[i].b, c = g[i].c; add(a, b, c), add(b, a, c); d[a]++, d[b]++; } int flag = 0; for (int i = 0; i < m; i++) { int a = g[i].a, b = g[i].b; if ((d[a] & 1) || (d[b] & 1)) { flag = 1; break; } } if (!flag) { dfs(1); // 逆序输出序列 for (int i = rl; i; i--) printf("%d ", res[i]); } else cout << "Round trip does not exist."; puts(""); } return 0; } ``` ### 四、$while$版本 ```cpp {.line-numbers} #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int N = 2010, M = N * N; // 声明结构体 struct Node { int a, b, c; bool const operator<(const Node &t) const { return c > t.c; } } g[N]; int st[M]; // 某条边是不是访问过,无向图一般用于处理成对就换的边 int d[N]; // 度 int res[M], rl; // 路径数组 int m; // m条边 // 链式前向星 int e[M], h[N], idx, w[M], ne[M]; void add(int a, int b, int c = 0) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; } void dfs(int u) { for (int i = h[u]; ~i; i = h[u]) { // 删边优化 h[u] = ne[i]; if (st[i]) continue; st[i] = st[i ^ 1] = 1; // 成对变换 dfs(e[i]); // 记录路径 res[++rl] = w[i]; } } int main() { #ifndef ONLINE_JUDGE freopen("POJ1041.in", "r", stdin); #endif int a, b, c; while (true) { memset(d, 0, sizeof d); memset(st, 0, sizeof st); memset(h, -1, sizeof h); memset(res, 0, sizeof res); idx = rl = m = 0; scanf("%d%d", &a, &b); if (a == 0 && b == 0) exit(0); scanf("%d", &c); g[m].a = a, g[m].b = b, g[m++].c = c; while (true) { scanf("%d%d", &a, &b); if (a == 0 && b == 0) break; scanf("%d", &c); g[m].a = a, g[m].b = b, g[m++].c = c; } // 针对边的边号进行由小到大排序 sort(g, g + m); for (int i = 0; i < m; i++) { int a = g[i].a, b = g[i].b, c = g[i].c; add(a, b, c), add(b, a, c); d[a]++, d[b]++; } int flag = 0; for (int i = 0; i < m; i++) { int a = g[i].a, b = g[i].b; if ((d[a] & 1) || (d[b] & 1)) { flag = 1; break; } } if (!flag) { dfs(1); // 逆序输出序列 for (int i = rl; i; i--) printf("%d ", res[i]); } else cout << "Round trip does not exist."; puts(""); } return 0; } ```