You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
96 lines
2.3 KiB
96 lines
2.3 KiB
#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 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 = 1; i <= rl; i++) printf("%d ", res[i]);
|
|
} else
|
|
cout << "Round trip does not exist.";
|
|
puts("");
|
|
}
|
|
return 0;
|
|
} |