题解 | L. 爆破鸭科夫

L. 爆破鸭科夫

我们定义 √ 为可以到达终点，× 为不可到达终点

随着炸弹的依次爆炸，状态分布为 "√√√√...××××"

也就是必定从连续的一段 √ 变化为连续的一段 ×，中间存在一个分界点

题目其实就是让我们求这个分界点对应的爆炸时间 ，输出

怎么找呢？如果我们二分，外层是 ，这里 为 上界，

内层的 需要判一次当前图连通性，是 的

事实上由于本题维护的是连通性，而连通性在 只加不删 的时候可以 并查集 直接维护

所以我们应该直接时光倒流，从炸完的状态往回跑，找到第一个连通的时间点，此时对应的就是那个恰好炸掉最后一条逃生路径的炸弹

这样时间复杂度就变成了

其中 指的是 并查集 的 反阿克曼函数，近似于 ，可直接记作

这里的并查集必须是 路径压缩+启发式合并 才能做到 的维护，否则是

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define fType int
#define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++)
#define foreach_sub(x, a, b) for (fType x = a, _end_ = b; x >= _end_; x--)
#define tpl make_tuple

struct Dsu
{
    vector<int> f, sz;

    Dsu(int ns) : f(ns + 1), sz(ns + 1, 1)
    {
        iota(f.begin(), f.end(), 0);
    }

    int getF(int x)
    {
        return f[x] == x ? x : f[x] = getF(f[x]);
    }

    void merge(int u, int v)
    {
        int fu = getF(u), fv = getF(v);
        if (fu == fv) return;

        if (sz[fu] > sz[fv]) swap(fu, fv);
        f[fu] = fv;
        sz[fv] += sz[fu];
    }
};

constexpr int N = 500010;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
ll delTime[N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    memset(delTime, 0x3f, sizeof delTime);

    int n, m, k, s, t;
    cin >> n >> m >> k >> s >> t;

    foreach (i, 1, k)
    {
        int x;
		ll time;
        cin >> x >> time;

        delTime[x] = min(delTime[x], time);
    }

    using pr = pair<ll, int>;
    vector<pr> bomb;
    bomb.reserve(k);
    foreach (i, 1, n)
        if (delTime[i] != INF) bomb.emplace_back(delTime[i], i);

    sort(bomb.begin(), bomb.end(), greater<pr>());

    Dsu dsu(n);
    vector<vector<int>> gp(n + 1);
    foreach (i, 1, m)
    {
        int u, v;
        cin >> u >> v;

        if (delTime[u] == INF && delTime[v] == INF)
            dsu.merge(u, v);
        else
            gp[u].emplace_back(v), gp[v].emplace_back(u);
    }

    for (auto [time, x] : bomb)
    {
        for (auto v : gp[x])
            if (delTime[v] == INF) dsu.merge(x, v);
        delTime[x] = INF;

        if (dsu.getF(s) == dsu.getF(t))
        {
            cout << time - 1 << "\n";
            return 0;
        }
    }

    return 0;
}

扩展思考：如果一个点有多个炸弹，该怎么写呢？