python

14 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##P3520 [POI2011] SMI-Garbage

LOJ 2162 垃圾运输 Garbage 注：LOJ果然是好东西，所有数据完整提供下载，真是太人性化，洛谷太垃圾了！

一、题目描述

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

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

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

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

二、输入格式

输入的第一行包含两个空格分隔的正整数 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 个空格分隔的整数，依次表示环路上结点的编号。

样例输入

样例输出

2
3 1 3 2 1
3 4 6 5 4

样例图示

二、题目解析

知识点：欧拉回路+异或+简单环

结合一下样例输出，明白了：

因为跑一趟就会让状态变成相反的，所以，如果前后一样的，其实没必要跑，或者要跑偶数次。如果前后不一样的，就需要跑一次或者跑奇数次。
- 如果原来是1，后来是1，或者，原来是0，后来是0，也就是红色虚线，只能走偶数数次。
- 如果原来是1,后来是0,或者，原来是0,后来是1,也就是黑色实线，只能走奇数次。
题目似乎在让我们找 简单环，两个输出示例，一个是上面的黑色线组成的环，另一个是下面黑色线组成的环。
什么情况下存在合法方案，什么情况下不存在合法方案呢？答：在以前后不一致的边抽出来建图(黑色线)，然后判断是不是每个点的度数都是偶数，就知道是不是每个点都在欧拉图中，如果有不存欧拉图中的，就是无法完成任务。

标准正确`dfs`答案

#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];    // 节点i是不是在栈内

void dfs(int u) {
    // u节点已访问过，之所以需要vist[u]这样的状态数组，本质上是因为本题是一张图中多组欧拉回路，
    // 没跑过的点才需要当做起点跑欧拉回路，需要记录哪个跑过哪个没跑过
    vist[u] = 1;

    for (int i = h[u]; ~i; i = h[u]) { // 枚举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号环中
            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); // 由于上面使用的是stk.back()!=v,这样是为了保持v还在栈中，让这个点重复命使用，可以参考图2的点3            
        } 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;
    scanf("%d %d", &n, &m); // 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);             // 双向建边,因为可以正着走，也可以反着走，但正反边只能走1次
            d[a]++, d[b]++;                   // 维护度
        }
    }

    // 检查是否某个点的度是奇数，这样没有欧拉回路
    for (int i = 1; i <= n; i++)
        if (d[i] % 2) {
            puts("NIE");
            exit(0);
        }

    // 遍历每个节点
    for (int i = 1; i <= n; i++)
        if (!vist[i] && d[i]) { // 如果节点i没有访问过，并且，是数据中出现过的点，比如1，2，5，6出现，3，4不参加讨论问题
            dfs(i);             // 对节点i进行深搜，找简单环
            /*简单环分两种情况：
            ① 出发点在内的简单环
            ② 在行进路线上出现的简单环
            这两种情况处理办法不一样，需要分别对待，下面就是情况①
            由于上面已经通过一笔画的定理排除掉了非欧拉回路的可能，现在的图肯定是欧拉回路
            那么，在dfs过程中我们可以把路径上的环处理掉，那么，一定有从起点出发的环还在栈中，需要单独处理
            */
            res[++rl].push_back(i);
            while (stk.size()) {
                res[rl].push_back(stk.back());
                instk[stk.back()] = 0;
                stk.pop_back();
            }
        }

    // 输出环的数量
    printf("%d\n", rl);

    // 遍历每个环
    for (int i = 1; i <= rl; i++) {
        printf("%d ", res[i].size() - 1); // 输出环中节点个数，这里为什么要减1呢？因为是环嘛，首尾是一样的，加入了两次
        for (auto x : res[i]) printf("%d ", x);
        puts("");
    }
    return 0;
}

三、代码解析

先给出一组测试数据：

我将按代码的执行流程来模拟一遍，可能挺长，耐心看完：

从1号点出发，因为1-4比1-7先给出，但由于 链式前向星是头插法，所以插入的在队头，所以先走7,也就是现在1->7的箭头方向
7->3,由于3->5是先给出的数据，3->6是后给出的数据，所以产生两个分支，一个向6前进，另一个向5前进,(为啥不先跑3->2?是因为3-2先给出，头插法，所以先跑5)
2准备走向3时，发现3已经在栈中了，也就是找到了一个简单环：将栈中元素准备弹出2，5
Q:为什么是2,5呢？3哪去了？因为3不能出栈！,原因很简单，这个点3除了在这个简单环以外，还在其它简单环中！如果我们把3也出了栈，后面的1,7,3,6,4,1中就没有了3, 那个就不是完整的简单环了！
那3不出栈，本简单环也不完整啊！是的，我们需要手动补上入口的3和出口的3

res[++rl].push_back(v); //入口的3

while (stk.back() != v) { //将栈中不包含3的节点记录到路径中
    res[rl].push_back(stk.back());
    instk[stk.back()] = 0;        
    stk.pop_back();               
}

res[rl].push_back(v); //出口的3

继续行进，3->6->4->1, 然后4号节点，执行了下面的代码

stk.push_back(v);     // 入栈
instk[v] = 1;         // 标识在栈内

将1号节点放入栈中。

至此，回到了1号节点，此时，由于1已经没有了出边，因为边都被我们删除掉了，可不没有了出边，递归终止了，没有机会将栈中存储的简单环路径：7,3,6,4保存成简单环！也就是在dfs(1)这样的起点后面，需要手动出栈，一出到底即可！不出干净还不行，会影响后面的其它环了~

res[++rl].push_back(i);
while (stk.size()) {
    res[rl].push_back(stk.back());
    instk[stk.back()] = 0;
    stk.pop_back();
}

四、并查集踩坑

我最开始错误的以为使用并查集一样可以完成任务，因为环嘛，当然是通过边相连的，如果用并查集维护，不就是可以找出哪些点通过边相连，而且，前面已经证明了存在欧拉回路，枚举每个家族的族长，以它为起点出发，不就可以找出所有环吗？

但事实证明我 错的离谱！原因是题目要求找出的是 简单环Simple \ Circle！比如下面的数据样例直接教你做人（参考下图中右侧部分）！我的答案就会把左边的那一大堆认为是一个环，可人家答案要求的是多个简单环，也就是：

3
3 3 5 2 3 
5 1 7 3 6 4 1 
3 9 13 14 9

我的答案是这样滴：

2
7 6 4 1 7 3 2 5 3 6 
3 13 14 9 13

这不是简单环，违背了原则：除起点外，其它点出现1次。节点3出现了两次，节点6出现了两次，是标准错误答案。

结论

这种找简单环，只能是用dfs，不能用并查集

标准错误并查集答案

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10, M = 2e6 + 10;

// 标准错误答案@！
// #2162. 「POI2011 R2 Day1」垃圾运输 Garbage
// https://loj.ac/s/1857935

// 并查集
int p[N], sz[N];
int find(int x) {
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}

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 st[M];

void dfs(int u) {
    for (int i = h[u]; ~i; i = h[u]) {
        h[u] = ne[i];
        if (st[i]) continue;
        st[i] = st[i ^ 1] = 1;
        int v = e[i];
        dfs(v);
        cout << u << " ";
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("P3520.in", "r", stdin);
#endif
    memset(h, -1, sizeof h);
    int n, m;
    scanf("%d %d", &n, &m);

    // 初始化并查集
    for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;

    int a, b, s, t;
    while (m--) {
        scanf("%d %d %d %d", &a, &b, &s, &t);
        if (s ^ t) {
            add(a, b), add(b, a);
            d[a]++, d[b]++;
            // 并查集
            int pa = find(a), pb = find(b);
            if (pa != pb) {
                p[pb] = pa;
                sz[pa] += sz[pb]; // 维护家庭人员数量
            }
        }
    }

    for (int i = 1; i <= n; i++)
        if (d[i] % 2) {
            puts("NIE");
            exit(0);
        }

    // 肯定是存在欧拉回路,现在是几个环呢？可以用并查集提前处理出来

    // 从头到尾，看一下有多少个家庭，就是有多少个环
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (d[i] && i == p[i]) cnt++;
    cout << cnt << endl;

    for (int i = 1; i <= n; i++)
        if (d[i] && i == p[i]) {
            cout << sz[i] << " " << i << " ";
            dfs(i);
            cout << endl;
        }
    return 0;
}

14 KiB Raw Permalink Blame History Unescape Escape