题解：P3520 [POI2011] SMI-Garbage

· · 题解

思路

通过观察发现，对于不需要改变状态的道路，即 s = t 的情况下，这种道路可以直接舍弃，并不会影响我们的答案。

比如考虑如下这张图：

9 10
1 2 0 1
2 3 0 1
3 4 0 1
4 5 0 1
5 6 0 1
6 7 0 1
7 8 0 1
8 9 0 1
9 1 0 1
3 7 0 0

发现 3 和 7 之间的边一开始就满足了条件，如果你硬要把它算进答案里，会得到下面的答案：

2
6 1 2 3 7 8 9 1
5 3 4 5 6 7 3

但是如果你当它不存在并不影响我们的正确性：

1
9 1 2 3 4 5 6 7 8 9 1

并且这样做有个好处就是我们不用处理这种特殊的边，毕竟不是每条 s = t 的边都像这样可以存在两条路径恰好路过它，所以决定把这种边忽视。

回到题目，注意看这个描述：除了起点以外不能跑两次。仔细思考，这不是欧拉回路吗（不知道的该去补课了）？所以问题就变成了：在一个无向图中找出所有的欧拉回路。

但是这题还有个小坑，就是题目虽然要求的是欧拉回路，但是也要求了除了起点以外不能跑两次，而欧拉回路的路径中只保证每条边只经过一次，并不保证每个点只经过一次。因此我们可以改造一下我们的搜索，记录每个节点是否出现过，如果已经出现过，可以从之前的位置到当前位置作一个新的欧拉路径。

代码

注意个细节，由于每个点可能属于不止一个欧拉回路，所以记录欧拉回路的数组要开大一点，hack 来自这篇帖子。

#include <iostream>
#include <vector>
using namespace std;
#define MAX_N 100005
#define MAX_M 2000005
struct Edge {
    int v, bind;
};
int idle = 1;
int head[MAX_N] = { 0 }, nex[MAX_M] = { 0 };
Edge edge[MAX_M] = { 0 };
void add(int u, int v, int b) {
    nex[idle] = head[u];
    head[u] = idle;
    edge[idle++] = { v, b };
}
int degree[MAX_N] = { 0 };
int blo = 0;
vector<int> block[MAX_N];
int id[MAX_N] = { 0 };
void dfs1(int node, int b) {
    id[node] = b;
    block[b].push_back(node);
    for (int ind = head[node]; ind; ind = nex[ind]) {
        int v = edge[ind].v;
        if (id[v]) continue;
        dfs1(v, b);
    }
}
bool vis[MAX_M] = { 0 };
int top = 0;
int stack[MAX_N] = { 0 };
int ans1 = 0;
vector<int> ans2[MAX_N << 2];
//标记前面是否出现过，在哪个下标出现的
int hit[MAX_N] = { 0 };
void dfs2(int u) {
    for (int& ind = head[u]; ind;) {
        int v = edge[ind].v;
        if (vis[ind]) {
            ind = nex[ind];
            continue;
        }
    //删边优化，如果一个图是单个点的超级自环，每次遍历同一个点的话会TLE
        vis[ind] = vis[ind + edge[ind].bind] = true;
        ind = nex[ind];
        dfs2(v);
    }
    if (hit[u]) {
        //发现一个新的欧拉回路
        ans1++;
        ans2[ans1].push_back(u);
        for (int x = hit[u] + 1; x <= top; x++) 
            ans2[ans1].push_back(stack[x]), hit[stack[x]] = 0;
        ans2[ans1].push_back(u);
        top = hit[u] - 1;
    }
    stack[++top] = u;
    hit[u] = top;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int x = 1; x <= m; x++) {
        int u, v, s, t;
        scanf("%d%d%d%d", &u, &v, &s, &t);
        if (s == t) continue;
        add(u, v, 1);
        add(v, u, -1);
        degree[u]++, degree[v]++;
    }
    for (int x = 1; x <= n; x++) if (!id[x]) dfs1(x, ++blo);
    for (int x = 1; x <= blo; x++)
        for (auto it : block[x])
            if (degree[it] % 2) {
                printf("NIE");
                return 0;
            }
    for (int x = 1; x <= blo; x++) {
        if (block[x].size() < 2) continue;
        top = 0;
        dfs2(block[x][0]);
    }
    printf("%d\n", ans1);
    for (int x = 1; x <= ans1; x++) {
        printf("%d", ans2[x].size() - 1);
        for (auto it : ans2[x]) printf(" %d", it);
        printf("\n");
    }
    return 0;
}