[P8383] [BZOJ2070] [POI2004] Bra

JCY_ · 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;
}