【题解/搜索】P6743 Senior Postmen

· · 题解

传送门

调了整整两天才过 qvq，在此感谢@北京大佬！

可以在 Starrykiller's blog 中阅读，或许会有更好的阅读体验。

题意简述

给出一张图，将其分成若干个环，其中这些环没有重复的边，且这些环覆盖了所有的点和边。

解法

考虑搜索。

我们有如下性质：若一个图的所有节点的度数均为偶数，则我们可以将这个图按题目要求分成不同的环。

我们不妨这么考虑：任选一个点作为起点进行 dfs（前提是经过的边没有访问过），并对访问过的边进行标记。

在 dfs 过程中，设当前点为 u。

（1）dfs 完后（for 循环结束后），如果 u 在栈中，这意味着我们之前已经访问过 u 了，栈中的序列是这个样子的：u, v_1, v_2, \cdots, v_n。我们将 v_1, v_2, \cdots, v_n 依次输出并出栈，取消标记，直到栈顶为 u 为止，v_1, v_2, \cdots, v_n 和点 u 共同构成了一个环。

大部分人可能用 while 来实现出栈的过程，需要注意的是，循环结束的时候，需要将栈顶的点（即点 u）一并输出并出栈。否则这个环是不完整的。

最后将 u 入栈，因为 u 可能被多个环所包含。

（2）若 u 不在栈中，我们将 u 入栈，并打上入栈标记。

这样直到 dfs 结束，我们就将图按题目的要求分成了一些互不相交的环。

Tips

Special Judge

该题目的 SPJ 并不会自动忽略行末空格（除最后一个空行外），会导致判定数字时加上空格而“不符合数字的格式”从而 WA，需要特殊处理。

优化

（1）

考虑 dfs 的过程，当前节点为 u，要访问的点为 v，边 u\to v 为 e(u, v)。

(a)若 e(u,v) 被访问过了，以后就不会再访问到了。我们可以令 head[u]=nxt[u]。

(b)若 e(u,v) 未被访问过，现在访问了，以后也不会再访问到了，同样可以令 head[u]=nxt[u]。

综上，我们在每次 for 循环时令 head[u]=nxt[u]。另外注意 for 循环更新为 i=head[u]，否则会导致效率大大降低。（TLE \to \sim 120 \text{ms}）

（2）使用 bitset 存储 vis 数组，或许可以提高效率和减少空间开销。

（3）合理使用快读和快写。

其实最重要的是优化 1，有了优化 1 之后其他都不重要，没有优化 1 只有优化 2、3 则很难 AC（当然也可能是我太菜了）。

代码

不要 copy 代码哦 www

const int MAXN=5e5+10, MAXM=1e6+10;
int n, m;
struct {
    int nxt, to;
} e[MAXM]; int head[MAXN], tot=1; // 双向边优化
inline void add(int u, int v) {
    e[++tot].to=v, e[tot].nxt=head[u], head[u]=tot;
}
bitset<MAXM> vis, in_stack;
int stk[MAXN], r;
inline void dfs(int u) { // 感谢rzy神！！！
    for (int i=head[u]; i; i=head[u]) {
    // 注意这里的循环赋值
        int to=e[i].to;
        head[u]=e[i].nxt; // 优化1
        if (vis[i]) continue;
        vis[i]=vis[i^1]=true;
        dfs(e[i].to);
    }
    // 进出栈过程
    if (in_stack[u]) {
        while (stk[r]!=u && r) {
            in_stack[stk[r]]=false;
            write(stk[r--]); putchar(' ');
        }
        write(stk[r--]); putchar('\n'); // 本题专属的SPJ优化
    }
    else in_stack[u]=true;
    stk[++r]=u;
}
int main() {
    n=read(), m=read();
    int x, y;
    for (int i=1; i<=m; ++i) {
        x=read(), y=read();
        add(x,y), add(y,x);
    }
    dfs(1);
    return 0;
}

这是 sk 酱的第一篇题解哦~

一定会有错误或者不足之处，欢迎大家指出，也请大家多多见谅 qaq

Reference

Solution on DM::OJ

Offical solution for BalticOI 2014 （虽然我没看懂）（悲）