自动搬运

查看原文

来自洛谷，原作者为

	JCY_ Nothing is wasted

搬运于2025-08-24 22:38:37，当前版本为作者最后更新于2022-09-13 11:37:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可能更好的阅读体验

题目大意

给你一个 $n$ 个点 $m$ 条边的有向图，从 $0$ 开始标号，有重边，有自环（$n\leq 10^4,m\leq 2\times 10^5$），每个点有三种状态 $0,\frac{1}{2},1$。

考察点 $u$，设在其所有前驱 $v$ 中，有 $c_0$ 个点状态为 $0$，$c_1$ 个点状态为 $1$，$c_2$ 个点状态为 $\frac{1}{2}$。若 $c_0>c_1$ 则点 $u$ 状态为 $0$，若 $c_0<c_1$ 则点 $u$ 状态为 $1$，否则点 $u$ 状态为 $\frac{1}{2}$。

现已知点 $0$ 的状态为 $0$，点 $1$ 的状态为 $1$，且这两个点入度均为 $0$。求在所有符合上述规则的状态分配中，状态均相同的点的标号，以及它们的状态。

分析

一眼看上去直接做有些困难，不妨考虑求出每个点状态大小的上界和下界，若上下界相同则说明其为所求点。上下界求法理应相同，所以只考虑如何求出下界。

先将点 $1$ 的状态赋为 $1$，其它点赋为 $0$。将点 $1$ 入队，然后开始进行类似 BFS 的调整：取出队首 $u$，遍历其所有后继 $v$，若此时 $v$ 的状态不符合规则，则修改 $v$ 的状态并将其入队。

正确性可以感性理解，因为每次调整都是必须的。

考虑分析这一过程的复杂度，不难发现每个点入队时状态大小必然变大，因此每个点入队不超过 $2$ 次，复杂度为 $O(m)$。

具体实现细节见代码。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 10;
int n, in[MAXN], c[MAXN][3], val0[MAXN], val1[MAXN], hd, tl, qu[MAXN * 2];
vector<int> g[MAXN];
inline int calc(int x) {
    if (c[x][0] > c[x][1]) return 0;
    if (c[x][1] > c[x][0]) return 1;
    return 2;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 2; i < n; ++i) {
        cin >> in[i];
        for (int j = 0, x; j < in[i]; ++j) {
            cin >> x;
            g[x].emplace_back(i);
        }
    }
    for (int i = 0; i < n; ++i) c[i][0] = in[i];
    val0[1] = 1;
    for (auto v : g[1]) --c[v][0], ++c[v][1];
    qu[hd = tl = 1] = 1;
    while (hd <= tl) {
        int u = qu[hd++];
        for (auto v : g[u]) {
            int t = calc(v);
            if (val0[v] != t) {
                for (auto w : g[v]) {
                    --c[w][val0[v]];
                    ++c[w][t];
                }
                qu[++tl] = v;
                val0[v] = t;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        c[i][1] = in[i];
        c[i][0] = c[i][2] = 0;
    }
    fill(val1 + 1, val1 + n, 1);
    val1[0] = 0;
    for (auto v : g[0]) --c[v][1], ++c[v][0];
    qu[hd = tl = 1] = 0;
    while (hd <= tl) {
        int u = qu[hd++];
        for (auto v : g[u]) {
            int t = calc(v);
            if (val1[v] != t) {
                for (auto w : g[v]) {
                    --c[w][val1[v]];
                    ++c[w][t];
                }
                qu[++tl] = v;
                val1[v] = t;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (val0[i] == val1[i]) {
            if (val0[i] == 2) {
                cout << "1/2";
            } else {
                cout << val0[i];
            }
        } else {
            cout << '?';
        }
        cout << '\n';
    }
    return 0;
}