洛谷P2731《骑马修栅栏 Riding the Fences》

一月 20, 2019 3762

欧拉图板子题

题目背景

Farmer John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。

题目描述

John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。

每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(>=1)个栅栏。两顶点间可能有多个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。

你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个 (也就是输出第一位较小的，如果还有多组解，输出第二位较小的，等等)。

输入数据保证至少有一个解。

输入输出格式

输入格式

第1行: 一个整数F(1 <= F <= 1024)，表示栅栏的数目

第2到F+1行: 每行两个整数i, j(1 <= i,j <= 500)表示这条栅栏连接i与j号顶点。

输出格式

输出应当有F+1行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。

输入输出样例

输入样例

1
2
3
4
5
6
7
8
9
10
9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6

输出样例

1
2
3
4
5
6
7
8
9
10
1
2
3
4
2
5
4
6
5
7

说明

题目翻译来自NOCOW。

USACO Training Section 3.3

解题思路

「使每个栅栏都恰好被经过一次」

妥妥的欧拉路板子题啊

没学过的看这里

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */
#include <map>
#include <cmath>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

namespace FastIO {
    
    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }
    
    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}


namespace Solution {
    const int MAXN = (500 + 10) << 1;
    
    int G[MAXN][MAXN], n, degree[MAXN];
    int __MAX_NODE = -1, __MIN_NODE = 0x7f7f7f7f;
    
    std::stack<int> ans;
    
    void addEdge(int from, int to) {
        ++G[from][to];
        ++G[to][from];
        ++degree[from];
        ++degree[to];
    }
    
    void Hierholzer(int s) {
        for (int t = __MIN_NODE; t <= __MAX_NODE; ++t) {
            if (G[s][t]) {
                --G[s][t];
                --G[t][s];
                Hierholzer(t);
            }
        }
        ans.push(s);
    }
}

signed main() {
#define HANDWER_FILE
#ifndef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    using namespace Solution;
    using namespace FastIO;
    n = getint();
    For (i, 1, n) {
        int prev = getint();
        int next = getint();
        addEdge(prev, next);
        __MAX_NODE = std::max(__MAX_NODE, std::max(prev, next));
        __MIN_NODE = std::min(__MIN_NODE, std::min(prev, next));
    }
    int start = 1, flag = 0;
    for (int i = 1; i <= __MAX_NODE; ++i, ++start) {
        if (degree[i] != 0 && degree[i] % 2 == 1) {
            flag = 1;
            break;
        }
    }
    if (flag) Hierholzer(start);
    else Hierholzer(1);
    while (!ans.empty()) {
        putint(ans.top(), '\n');
        ans.pop();
    }
    return 0;
}