题解：P13548 [OOI 2022] Air Reform

pipilong2024 · 2026-04-25 17:52:27 · 题解

这真是神仙题了。爆肝我 8days，看来还是太菜了。

大概转化一下题意：就是说给你一张无向连通图，你需要建它的一个补图，其中补图两点的边权就是在原图中两点最小瓶颈路的最大边权，你需要求出对于原图的每条边 (u,v)，求两点在补图中最小瓶颈路的最大边权。

对于最小瓶颈路的最大边权，这个东西显然可以用 Kruskal 重构树解决，求一个 LCA 即可。
所以算法瓶颈在于怎么快速建出补图的重构树。

考虑暴力，注意到在建原图的重构树时是从小到大枚举边权建新节点的，所以我们考虑在每次建新节点的时候枚举左右两个子树集合，若两点在原图中没有边且在补图中还未连通，则连一条边。
可以得到 21pts 的高分。 ::::warning[21pts]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int maxn = 3e5 + 10;
int T, g, n, m, q, cnt;
struct Node {
    int u, v, w;
    bool operator<(const Node &ppl)const & {
        return w < ppl.w;
    }
} e[maxn], _[maxn];
int val[maxn], f[maxn][21], dep[maxn];
vector<int>son[maxn];
map<pii, int>mp;
struct dsu {
    int fa[maxn];
    void init(int n) {
        for (int i = 1; i <= n; i++) fa[i] = i;
    }
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
} B1, B2;
int LCA(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    int d = dep[x] - dep[y];
    for (int i = 20; i >= 0; i--) if (d >> i & 1) x = f[x][i];
    if (x == y) return x;
    for (int i = 20; i >= 0; i--) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}
void init() {
    mp.clear();
    for (int i = 1; i <= n; i++) son[i].clear();
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T >> g;
    while (T--) {
        init();
        cin >> n >> m;
        for (int i = 1, u, v, w; i <= m; i++) {
            cin >> u >> v >> w;
            mp[ {u, v}] = mp[ {v, u}] = 1;
            _[i] = e[i] = {u, v, w};
        }
        sort(e + 1, e + m + 1);
        for (int i = 1; i <= n; i++) son[i].push_back(i);
        B1.init(n), B2.init(n);
        int _cnt = n;
        cnt = n;
        for (int i = 1; i <= m; i++) {
            int fu = B1.find(e[i].u), fv = B1.find(e[i].v), w = e[i].w;
            if (fu == fv) continue;
            _cnt++;
            B1.fa[_cnt] = B1.fa[fu] = B1.fa[fv] = _cnt;
            for (auto x : son[fu]) for (auto y : son[fv]) {//暴力枚举左右子树 
                    if (mp[ {x, y}]) continue;
                    int fx = B2.find(x), fy = B2.find(y);
                    if (fx == fy) continue;
                    val[++cnt] = w;
                    f[fx][0] = f[fy][0] = cnt;
                    B2.fa[cnt] = B2.fa[fx] = B2.fa[fy] = cnt;
                }
            son[_cnt].clear();
            for (auto x : son[fu]) son[_cnt].push_back(x);
            for (auto x : son[fv]) son[_cnt].push_back(x);
            son[fu].clear(), son[fv].clear();
        }
        for (int k = 1; k <= 20; k++) for (int i = 1; i <= cnt; i++) f[i][k] = f[f[i][k - 1]][k - 1];
        dep[cnt] = 1;
        for (int i = cnt - 1; i >= 1; i--) dep[i] = dep[f[i][0]] + 1;
        for (int i = 1; i <= m; i++) {
            int u = _[i].u, v = _[i].v;//查原图的边 
            cout << val[LCA(u, v)] << " ";
        }
        cout << "\n";
    }
    return 0;
}

:::: 考虑优化。

为了方便表示，对于当前节点 u，不妨设其左右子树分别含 id_l 和 id_r 个联通块，st_x 表示第 x 个连通块中的元素个数。

考虑如何合并 u 左右子树的连通块。

不妨先枚举左右子树的连通块 id_l 和 id_r，用 idx 和 idy 表示，再枚举每个连通块中间的元素 st_{idx} 和 st_{idy}，用 x 和 y 表示，若两点在原图中没有边，且在补图中尚未连通，则将两点相连（到这里和暴力是一样的）。