[POI2011] SMI-Garbage Solution

· · 题解

[POI2011] SMI-Garbage Solution

题意描述

一条路有两种状态，每次访问会改变路的状态。显然，初始状态与目标状态相同的路并不需要加入这个无向图，因此题意转为：给定一个无向图，求所有简单环。

解法分析

由求简单环不难想到欧拉回路，由欧拉回路性质知，无向图中不存在欧拉回路的条件是存在度数为奇数的点，至此，无解情况处理完毕。利用一个元素两次出现来判断是否存在一个环，若出现环，将其输出到一个 vector 中存储。

参考代码

#include <bits/stdc++.h>
#define upf(i, n, k) for (int i = k; i <= n; i++)
#define lowf(i, n, k) for (int i = n; i >= k; i--)
#define Max(a, b, c) max(a, max(b, c))
#define Min(a, b, c) min(a, min(b, c))
#define ofile(N) freopen(N ".in", "r", stdin), freopen(N ".out", "w", stdout)
#define ri register int
#define ie inline
#define ll long long
#define read() input<int>()
#define readll() input<ll>()
using namespace std;

template <typename TT>
ie TT input() {
    TT s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

template <typename TT>
ie void out(TT a) {
    if (a < 0) putchar('-'), a = -a;
    if (a >= 10)
        out(a / 10);
    putchar(a % 10 + '0');
}

const int mn = 1e6 + 5;
int n, m, x, y, now, tar, cnt, nb, vis[10000010], dg[mn], viss[mn], ins[mn];
int head[mn << 1], nxt[mn << 1], ver[mn << 1], tot;
inline void add(int u, int v) {
    ver[tot] = v, nxt[tot] = head[u], head[u] = tot++;
}
vector<int> ret[mn << 1];
stack<int> s;

inline void dfs(int u) {
    viss[u] = 1; //标记该点是否走过
    for (ri i = head[u]; ~i; i = nxt[i])
        if (!vis[i]) {
            vis[i] = vis[i ^ 1] = 1; //标记边是否经过
            head[u] = nxt[i]; //当前弧优化
            int v = ver[i];
            dfs(v);
        }
    if (ins[u]) {
        ret[++cnt].push_back(u);
        while (s.top() != u) ret[cnt].push_back(s.top()), ins[s.top()] = 0, s.pop();
        ret[cnt].push_back(u); //保存答案
    } else
        s.push(u), ins[u] = 1;
}

int main() {
    memset(head, -1, sizeof head);
    n = read(), m = read();
    for (ri i = 1; i <= m; i++) {
        x = read(), y = read(), now = read(), tar = read();
        if (now ^ tar) add(x, y), add(y, x), dg[x]++, dg[y]++;
    }
    for (ri i = 1; i <= n; i++)
        if (dg[i] & 1) return puts("NIE"), 0; //欧拉回路判断无解
    for (ri i = 1; i <= n; i++)
        if (!viss[i]) 
            dfs(i);
    out(cnt), puts("");
    for (ri i = 1; i <= cnt; i++) {
        out(ret[i].size() - 1), putchar(' ');
        for (auto j : ret[i])out(j), putchar(' ');
        puts("");
    }
    return 0;
}

后记

本题细节较多，作者太菜了调了许久，作题解以纪念。

是道锻炼思维/练习欧拉回路的好题。