SMI-Garbage

· · 题解

SMI-Garbage

题目描述

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

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

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

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

判断无解

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

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

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

// 初始化邻接表头指针 
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;

找简单环

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

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

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

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

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

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

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

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);         // 找包含这个点的环

代码

放这了。