题解：P11360 [CEOI2015] 管道

WorldMachine · 2024-12-09 22:33:23 · 题解

小水题，之前想过这样的东西，碰巧看到了这道题就做一下吧。

这个题 tarjan 肯定是做不了的，因为 \mathcal O(m) 的空间开不下。

割边一定在生成树上，那我们弄出原图的一棵生成树，现在就是要求有哪些树边没有被覆盖。对每条非树边 (u,v)，我们随机一个权值 w，将 a_u 加上 w，a_v 减去 w。这样 (u,v) 这条边的影响刚好会在 \text{lca}(u,v) 处被消去，随机权值下如果 v 子树内的 a_i 之和为 0，那么 (\text{fa}_v,v) 有很大概率是一条割边。

时间复杂度 \mathcal O(n\alpha(n)+m)，瓶颈在于并查集，所以通常情况下没啥优势。

代码已省去快读。

#include <bits/stdc++.h>
using namespace std;
// namespace IO
#define cin io
#define cout io
typedef long long ll;
const int N = 100005, M = 6e6 + 5;
int n, m, fa[N], siz[N];
ll a[N];
vector<int> G[N];
mt19937 rnd(time(0));
int get(int x) { return x == fa[x] ? x : fa[x] = get(fa[x]); }
void dfs(int u, int f) {
    for (int v : G[u]) {
        if (v == f) continue;
        dfs(v, u), a[u] += a[v];
        if (!a[v]) cout << u << ' ' << v << '\n';
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1;
    int u, v, fu, fv;
    ll w;
    while (m--) {
        cin >> u >> v;
        fu = get(u), fv = get(v);
        if (fu != fv) {
            if (siz[fu] > siz[fv]) swap(fu, fv);
            fa[fu] = fv, siz[fv] += siz[fu];
            G[u].emplace_back(v), G[v].emplace_back(u);
        } else w = rnd(), a[u] += w, a[v] -= w;
    }
    for (int i = 1; i <= n; i++) if (i == fa[i]) dfs(i, 0);
}