Skip to content

「POI2011 R2 Day1」垃圾运输 Garbage

题解约 1 千字
# 洛谷 # LibreOJ # 2011 # 图论 # POI # 欧拉图 # 欧拉回路
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

译自 POI 2011 Round 2. Day 1. B「Garbage」

给定一张 nn 个点 mm 条边的无向图，每条边居黑白二色之一，且有一个黑或白的目标颜色。

有一辆卡车，可以从任意一个结点开始，经过一个简单环（不经过重复边或起点以外结点的环）回到出发点，将所有经过边的颜色反转，即黑色变为白色，白色变为黑色。卡车可以从不同的结点出发行走若干次。

请给出一个合法的方案，使得每条边最终都变为目标颜色，或判定不可行。

#输入格式

输入的第一行包含两个空格分隔的正整数 nn 和 mm，表示图的点数和边数。

接下来 mm 行，每行包含四个空格分隔的正整数 a,b,s,ta, b, s, t，表示一条联结结点 aa 与 bb 的边，初始颜色和目标颜色分别为 ss 与 tt。

你可以认为若存在合法方案，则存在一个卡车经过总边数不超过 5m5m 的方案。

#输出格式

如果不存在合法方案，输出一行 NIE（波兰语「否」）；

否则按下列格式输出任意一种方案：

  • 第一行包含一个整数 kk，表示卡车行驶环路的总数；
  • 接下来 kk 行，每行描述一条环路：
    • 首先是一个正整数 kik_i 表示环路经过的边数，后接一个空格；
    • 接下来 ki+1k_i + 1 个空格分隔的整数，依次表示环路上结点的编号。

#输入输出样例

样例输入 #1

6 8
1 2 0 1
2 3 1 0
1 3 0 1
2 4 0 0
3 5 1 1
4 5 0 1
5 6 0 1
4 6 0 1

输出样例 #1

2
3 1 3 2 1
3 4 6 5 4

样例解释 #1

样例输入 #2

6 8
1 2 0 1
2 3 1 0
1 3 0 1
2 4 0 0
3 5 1 1
4 5 0 1
5 6 0 1
4 6 0 0

样例输出 #2

NIE

样例解释 #2

#数据范围与提示

  • 对于 60%60\% 的数据，有 m≤10000m \leq 10000；
  • 对于 100%100\% 的数据，1≤n≤1051 \leq n \leq 10^5，1≤m≤1061 \leq m \leq 10^6，1≤a<b≤n1 \leq a \lt b \leq n，s,t∈{0,1}s, t \in \{0, 1\}。

#思路

读题可知本题需要在图中求出若干个欧拉回路。

显然，没有改变权值的边可以直接忽略掉。之后计算每个点的度数，根据欧拉回路的定义，图中不能存在度数为奇数的点，如果发现图中存在度数为奇数的点则无解。

之后使用 dfs 求出这些欧拉回路即可。

#代码

C++
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
#include <iostream>
#include <stack>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e5 + 5,
          M = 1e6 + 5;

int n, m, d[N], root;
bool vis[N], in_stack[N], edge_used[M];
std::stack<int> st;
std::vector<std::pair<int, int>> g[N];
std::vector<std::vector<int>> ans;

void dfs(int u) {
    vis[u] = true;

    for (auto e : g[u]) {
        int v = e.first,
            id = e.second;

        if (edge_used[id]) continue;
        edge_used[id] = true;

        dfs(v);
    }

    if (in_stack[u]) {
        std::vector<int> res{u};

        while (st.top() != u) {
            res.emplace_back(st.top());
            in_stack[st.top()] = false;
            st.pop();
        }

        res.emplace_back(u);
        ans.emplace_back(res);
    } else {
        st.push(u);
        in_stack[u] = true;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1, a, b, s, t; i <= m; i++) {
        cin >> a >> b >> s >> t;

        if (s ^ t) {
            g[a].emplace_back(b, i);
            g[b].emplace_back(a, i);

            d[a]++, d[b]++;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (d[i] % 2 != 0) {
            cout << "NIE" << endl;

            exit(0);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) dfs(i);
    }

    cout << ans.size() << endl;

    for (auto& item : ans) {
        cout << item.size() - 1 << ' ';

        for (int& x : item) {
            cout << x << ' ';
        }

        cout << endl;
    }

    return 0;
}