P3520 [POI2011] SMI-Garbage
\(P3520\) \([POI2011]\) \(SMI-Garbage\)
题目描述
有一个可以看成无向图的城市，上面有 \(n\) 个点和 \(m\) 条边。
每一天，有若干辆垃圾车按照环形来跑一圈。并且，对于一辆垃圾车， 除了起点以外不能跑两次。
一条路有 \(2\) 种状态：清洁的（用 0 表示）或不清洁的（用 1 表示）。每次垃圾车经过，都会改变这条路的状态。
因为有些路上的人不交垃圾清理费，所以市长想要那些路变得不清洁；除此之外的路要清洁。那么，如何安排垃圾车，才能使得市长目的达到呢？
By @dengziyue
感谢 @cn：苏卿念 提供\(SPJ\)
输入格式
输入的第一行包含两个空格分隔的正整数 \(n\) 和 \(m\) \(（ 1 \leqslant n \leqslant 100000，1 \leqslant m \leqslant 1000000）\)，表示图的点数和边数。
接下来 \(m\) 行，每行包含四个空格分隔的正整数 $a,b,s,t $（ $1 \leqslant a \leqslant b \leqslant n $ , \(s，t \in \lbrace0,1\rbrace\) ） ，表示一条联结结点 \(a\) 与 \(b\) 的边，初始颜色和目标颜色分别为 \(s\) 与 \(t\) 。
你可以认为若存在合法方案，则存在一个卡车经过总边数不超过 \(5m\) 的方案。
对于 \(60\%\) 分数的数据，有 $ m \leqslant 10000$。
输出格式
如果不存在合法方案，输出一行 NIE（波兰语「否」）；
否则按下列格式输出任意一种方案：
- 第一行包含一个整数 \(k\)，表示卡车行驶环路的总数；
- 接下来 \(k\) 行，每行描述一条环路：
- 首先是一个正整数 \(k_i\) 表示环路经过的边数，后接一个空格；
- 接下来 $ k_i + 1 $ 个空格分隔的整数，依次表示环路上结点的编号。
样例 #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\)，后来是\(1\)，或者，原来是\(0\)，后来是\(0\)，也就是红色虚线，只能走偶数数次，或者说走\(2\)次。
- 如果原来是\(1\),后来是\(0\),或者，原来是\(0\),后来是\(1\),也就是黑色实线，只能走奇数次，或者说走\(1\)次。
-
题目似乎在让我们找环，两个输出示例，一个是上面的黑色线组成的环，另一个是下面黑色线组成的环。
-
什么情况下存在合法方案，什么情况下不存在合法方案呢？
答：在以前后不一致的边抽出来建图，然后判断是不是每个点的度数都是偶数，就知道是不是每个点都在欧拉图中，如果有不存欧拉图中的，就是无法完成任务。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2e6 + 10;
// 链式前向星
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++;
}
int d[N]; // 度
vector<int> res[N]; // 每个环中有哪些节点
int rl; // 环的数量，游标
int vist[N]; // 某个点是不是访问过
int st[M]; // 边是不是访问过
vector<int> stk; // 节点存储栈
int instk[N]; // 是不是在栈内
/*
每次要求走过一个简单环上的边，即从某个点开始走过该点存在的联通图（原图可能不联通），
初始权值与最终权值相等的边走偶数次，不相等的走奇数次。
为什么用欧拉回路？
欧拉回路：存在一条从某个点开始，恰好不重不漏经过每条边一次（点可重复），最终回到该点。
欧拉图：存在欧拉回路的图。
欧拉图的判定：每个点的度数都为偶数。
通过以上定义和判定，可以考虑权值不相等的边通过找欧拉回路的方法来。因为依题意，权值相等的边必须走偶数次才能达到目标，
而欧拉图只要求走一次，和欧拉图不一致。
权值相等的边，因为每次都必须走偶数次，相当于拆成了两条边，这样实际上就使得该边对连接的两点度数加了+2，
根据欧拉回路的定义，删去这条边即对两点度数-2，还使得图成为欧拉图了（只用走剩下的边一次），就可以直接找欧拉回路了。
*/
// 在求欧拉回路的过程中，找环，记录下有几个环，都是啥节点
void dfs(int u) {
// u节点已访问过，之所以需要vist[u]这样的状态数组，本质上是因为本题是一张图中多组欧拉回路，
// 没跑过的点才需要当做起点跑欧拉回路，需要记录哪个跑过哪个没跑过
// 所以说，对于标准模板的话，是没有这句的
vist[u] = 1;
for (int i = h[u]; ~i; i = ne[i]) { // 枚举u节点的每个出边i
h[u] = ne[i]; // 为了防止回溯时重复跑，性能慢，删边,性能优化
if (st[i]) continue; // 此边访问过，不用再讨论
st[i] = st[i ^ 1] = 1; // 无向图，成对标识已被访问过
int v = e[i]; // 节点u通过边i指向点v
dfs(v); // 深搜v=e[i]这个点
if (instk[v]) { // 如果v点在栈中，说明找到了环
res[rl].push_back(v); // v记录到rl号环中
// 这里无法用类似 int x=stk.back()的办法进行精简代码，那样就失去了stk.back()的动作，导致下面的代码失效
while (stk.back() != v) { // 一直把栈顶元素弹出，直到找出首次进入的那个v，也就是通过栈找环
res[rl].push_back(stk.back()); // 将环中的节点记录到res[rl]这个结果集中去
instk[stk.back()] = 0; // 标识栈顶元素已出栈
stk.pop_back(); // 栈顶元素出栈
}
res[rl].push_back(v); // 同一个节点出现两次，记录两次，这才是环,题目要求输出这样的格式
++rl; // 环的数量+1
} else { // 如果不在栈内
stk.push_back(v); // 入栈
instk[v] = 1; // 标识在栈内
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("P3520.in", "r", stdin);
#endif
memset(h, -1, sizeof h); // 初始化链式前向星
int n, m; // n个顶点，m条边
scanf("%d %d", &n, &m);
int a, b, s, t;
while (m--) {
scanf("%d %d %d %d", &a, &b, &s, &t); // a到b有一条边，颜色初始值是s,目标终止值是t
if (s ^ t) { // 如果s与t不一样,建边。因为需要走偶数次，不符合欧拉图定义
add(a, b), add(b, a); // 双向建边
++d[a], ++d[b]; // 维护度
}
}
// 检查是否某个点的度是奇数，这样没有欧拉回路
for (int i = 1; i <= n; i++)
if (d[i] % 2) {
puts("NIE");
return 0;
}
// 遍历每个节点
for (int i = 1; i <= n; i++)
if (!vist[i]) { // 如果节点i没有访问过
dfs(i); // 对节点i进行深搜
if (instk[i]) { // 如果此节点i在栈中，表示找到了环。栈是本轮的概念，本轮跑圈中是不是重现节点i,这表示有环
res[rl].push_back(i); // 第rl个环中，增加i这个节点号
while (stk.size()) { // 利用循环，把栈中所有节点出栈，记录到结果数组中
res[rl].push_back(stk.back()); // 将栈中记录的节点，都增加到rl这个环中去
instk[stk.back()] = 0; // 记录这个节点已经出栈
stk.pop_back(); // 节点出栈
}
++rl; // 环数量+1
}
}
// 输出环的数量
printf("%d\n", rl);
// 遍历每个环
for (int i = 0; i < rl; i++) {
printf("%d ", res[i].size() - 1); // 输出环中节点个数，这里为什么要减1呢？因为是环嘛，首尾是一样的，加入了两次
for (auto x : res[i])
printf("%d ", x);
puts("");
}
return 0;
}