CF 1795G Removal Sequences

标签: cf

给定一个无向图,每个点有一个权值 ,节点 可以被删当且仅当 的入度等于 。要把整个图删光,存在许多删除序列,问有多少个二元组 ,使得在某个删除序列中, 先删,而在另一个删除序列中, 先删。保证存在至少一个删除序列。

求这样的二元组比较麻烦,考虑求其反面,即删除顺序确定的二元组

首先,在删除的某个阶段,容易证明所有满足可删条件的点不相邻,换句话说,相邻的点被删的阶段一定不同。因为如果存在相邻,那么删除某一个,另一个入度减小,再也无法被删,与条件矛盾。

所以我们可以先 bfs 求出每个点被删除的阶段 ,那么对于相邻的两个点, 较小的一定在 较大的之前被删。考虑给每条边定向,从 较小的点指向较大的点,可以发现这个图一定是一个有向无环图。那么 之前被删就等价于可以从 到达 ,问题就转变成统计有向无环图上的可达性统计。这个问题十分经典,令 表示第节点 能否到达 ,则按照拓扑排序反向转移即可。

然而这样做是 的,无论内存还是时间上都无法通过。我们进行一些常数优化,将 定义成 uint64_t,并 64 个一组处理,假设当前是第 组,那么 可以到 就表示成 。这样空间复杂度就是 的,每组的 数组可以循环利用。而时间复杂度并没有优化,但常数优化了,可以通过此题。

代码很丑,推荐直接看题解。

struct graph
{
    vector<vector<int>> e;
    vector<int> indeg;
    graph(int n) : e(n), indeg(n) {}
};
 
struct directed_graph: public graph
{
    void add_edge(int u, int v)
    {
        // printf("add directed edge %d %d\n", u, v);
        e[u].emplace_back(v);
        indeg[v]++;
    }
    vector<int> sort()
    {
        int n = e.size();
        vector<int> res;
        res.reserve(n);
        std::queue<int> q;
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                q.emplace(i);
            }
        }
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            res.emplace_back(u);
            for (auto v : e[u]) {
                indeg[v]--;
                if (indeg[v] == 0) {
                    q.emplace(v);
                }
            }
        }
        return res;
    }
    long long count_approach()
    {
        int n = e.size();
        long long res = 0;
        auto seq = sort();
        // std::reverse(seq.begin(), seq.end());
        for (int i = 0; i * 64 < n; i++) {
            vector<uint64_t> f(n);
            int l = i * 64, r = (i + 1) * 64;
            for (auto j : seq) {
                if (l <= j && j < r) f[j] |= 1ull << (j - l);
                res += std::popcount(f[j]);
                for (auto v : e[j]) {
                    f[v] |= f[j];
                }
            }
        }
        return res;
    }
};
 
struct origin_graph : public graph
{
    vector<int> a;
    origin_graph(int n) : graph(n), a(n) {}
    void read(int m)
    {
        int n = e.size();
        for (auto &i : a) cin >> i;
        for (int i = 0; i < m; i++)
        {
            int u, v;
            cin >> u >> v;
            add_edge(u - 1, v - 1);
        }
    }
    void add_edge(int u, int v)
    {
        e[u].emplace_back(v);
        e[v].emplace_back(u);
        indeg[u]++;
        indeg[v]++;
    }
    directed_graph bfs()
    {
        int n = e.size();
        directed_graph res(n);
        vector<int> lvl(n);
        std::queue<std::pair<int, int>> q;
        for (int i = 0; i < n; i++) {
            if (indeg[i] == a[i]) {
                q.emplace(i, 0);
            }
        }
        while (!q.empty())
        {
            auto [u, l] = q.front();
            q.pop();
            lvl[u] = l;
            for (auto v : e[u]) {
                indeg[u]--;
                indeg[v]--;
                if (indeg[v] == a[v]) {
                    q.emplace(v, l + 1);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (auto j : e[i]) {
                if (lvl[i] > lvl[j]) res.add_edge(i, j);
            }
        }
        return res;
    }
};
 
void solve()
{
    int n, m;
    cin >> n >> m;
    origin_graph g(n);
    g.read(m);
    auto ng = g.bfs();
    cout << (long long)n * (n - 1) / 2 + n - ng.count_approach() << endl;
}