SMI-Garbage - 洛谷保存站

# [SMI-Garbage](https://www.luogu.com.cn/problem/P3520)

## 题目描述

有一个可以看成无向图的城市，上面有 $n$ 个点和 $m$ 条边。

每一天，有若干辆垃圾车按照**环形**来跑一圈。并且，**对于一辆垃圾车，** 除了起点以外不能跑两次。

一条路有 $2$ 种状态：清洁的（用 `0` 表示）或不清洁的（用 `1` 表示）。每次垃圾车经过，都会改变这条路的状态。

因为有些路上的人不交垃圾清理费，所以市长想要那些路变得不清洁；除此之外的路要清洁。那么，如何安排垃圾车，才能使得市长目的达到呢？

## 判断无解

由于每条边最多经过一次，所以如果存在一条边的初始状态与目标状态相同，那么一定不会走到这条边上，也就不需要建一条这样的边了。

建完图后，考虑 `NIE` 的情况。

分析题意，不难知道题目相当于是要用若干个简单环铺满整张图。而如果有若干个简单环连在一起，这就相当于是一条一个连通块内欧拉回路。所以判断是否无解，只需要按照欧拉回路的判断方法，看每个点的度数是否都为偶数即可。

```cpp
// 初始化邻接表头指针 
memset(h, -1, sizeof h);

// 读入 
n = read(), m = read();

for (int i = 1; i <= m; i ++ )
{
	int a = read(), b = read();
	if (read() != read())		// 只有在初始状态与目标状态不同时才会建边 
	{
		add(a, b), add(b, a);
		d[a] ++ , d[b] ++ ;		// 统计度数 
	}
}

for (int i = 1; i <= n; i ++ )
	if (d[i] & 1)		// 如果存在点的度数为奇数，输出 NIE 结束 
		return puts("NIE"), 0;
```

## 找简单环

上面有提到过，题目相当于是要用若干个简单环铺满整张图。那么接下来就需要找到这些简单环。

在这之前，我们先定义一些将要用到的东西：

- $st_i$ 表示第 $i$ 条边是否被删除；
- $vis_i$ 表示第 $i$ 个点是否被一个简单环覆盖过；
- $instk_i$ 表示第 $i$ 个点是否在栈中。

对于每个点，如果它还没有被之前的一个简单环覆盖过，也就是 $vis_i = \mathrm{false}$，就以它做起点找环，具体来说从它开始 `DFS`。

从这个点 $u$ 出发，找到它的临点 $j$，并删掉 $u \longleftrightarrow j$ 这条边。然后 `DFS(j)`，继续搜索 $j$ 的临边。

在点 $u$ 的其它点都搜索完后，我们尝试把 $u$ 加入栈中。

如果它本来不在栈中，那么入栈并标记 $instk_u = \mathrm{true}$。

如果它本来在栈中，那么就说明这个点在刚才被搜索过，也就代表这里出现了一个环。此时把栈中 $u$ 之前的所有元素弹栈，并存入最终答案中。

```cpp
void dfs(int u)
{
	vis[u] = true;		// 标记访问过这个点 
	for (int i = h[u]; ~i; i = ne[i])		// 枚举 u 的出边 
	{
		if (st[i]) continue;		// 如果这条边已经被删除了，不做考虑 
		st[i] = st[i ^ 1] = true;	// 删除这条边 
		int j = e[i];
		h[u] = ne[i];		// 当前弧优化 
		dfs(j);		// 继续搜索 
	}
	
	// 接下来要考虑把 u 加入栈中 
	if (in_stk[u])		// 如果 u 已经在之前的搜索中加入栈了，也就说明找到了一个环 
	{
		++ k;		// 车辆数加一 
		v[k].pb(u);		// 存入答案 
		for (int t = s.top(); t != u; t = s.top())	// 弹出 u 之前的所有元素 
		{
			v[k].pb(t);			// 存入答案 
			in_stk[t] = false;	// 标记出战 
			s.pop();			// 出栈 
		}
		v[k].pb(u);		// 由于是一个环，所以有两个 u 点 
	}
	else		// 否则如果本来不在环中 
	{
		s.push(u);		// 入栈 
		in_stk[u] = true;		// 标记入栈 
	}
}

for (int i = 1; i <= n; i ++ )
	if (!vis[i])		// 如果 i 点还没有被之前的一个环覆盖过
		dfs(i);			// 找包含这个点的环
```

## 代码

放[这](https://www.luogu.com.cn/paste/1aokxysk)了。

正在渲染内容...