Skip to content

「POI2011 R2 Day1」垃圾运输 Garbage

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

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

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

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

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

#输入格式

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

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

你可以认为若存在合法方案,则存在一个卡车经过总边数不超过 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\% 的数据,有 m10000m \leq 10000
  • 对于 100%100\% 的数据,1n1051 \leq n \leq 10^51m1061 \leq m \leq 10^61a<bn1 \leq a \lt b \leq ns,t{0,1}s, t \in \{0, 1\}

#思路

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

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

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

#代码

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;
}