P3206 [HNOI2010]城市建设 题解

· · 题解

相对于一般的 CDQ 分治，这题的写法略有不同。相信也难倒了不少初学者，那么我就来带大家分析一下。

如果是暴力每次跑一次 kruskal，时间复杂度肯定要爆炸。但我们可以通过分治，一层层的统一求出一定用到的边和一定用不到的边，达到减少边数的效果，最后到达边界时再进行暴力，可以起到很好的加速效果。本质上就是将单独选边转化为给一个区间的所有询问选边，起到优化时间的效果。

具体的，我们的函数 CDQ(l, r) 就是要删除对于 l, r 中的讯问，能够确定一定选或者一定不选的边。

具体的，我们把 [l,r] 中要修改的边的权值都改为 -\infty，再与当前边集 f 中的边跑一次最小生成树，把 f 中的边两边端点直接进行缩点（合并）。由于 f 中的边一定能形成一棵生成树（因为原图存在生成树，并且每次分治的时候，该计算过程只删了一定不选的边，而一定选的边也进行了缩点，所以必定存在生成树），所以最多只是那 r - l + 1 个修改的边的端点没有连到一起，所以点的个数为 O(r - l + 1)。

然后，我们再把 [l,r] 中要修改的边的权值都改为 +\infty，再与当前边集 f 中的边跑一次最小生成树（f 已经经过缩点）。没有选上的边就是无用的边，边的个数与点同阶，为 O(r-l+1)。

而计算顺序是：先按顺序执行上述计算，再计算 CDQ(l,mid)，再计算 CDQ(mid+1,r)。只有这样才能保证计算 CDQ(l,r) 时， 1 到 l- 1 的所有边权都修改了过来。而上述两步计算出来的边是在不管 [l,r] 怎么修改边权都成立的，所以没有关系。最后，我们带着计算出来的边，进行下一层递归即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5, INF = 1e8;
using LL = long long;
int n, m, qq, c[N], ct[N], a[N], b[N], fa[N];
LL ans[N];
struct P {
    int x, y, z, id;
    bool operator < (const P &a) const {
        return z < a.z;
    }
} e[20][N], f[N], g[N];
int get(int x) {
    return fa[x] == x ? x : fa[x] = get(fa[x]);
}
void Clear(int tot) {
    for (int i = 1; i <= tot; ++i) {
        fa[f[i].x] = f[i].x;
        fa[f[i].y] = f[i].y;
    }
}
void CDQ(int l, int r, int now, int tot, LL sum) {
    if (l == r) ct[a[l]] = b[l];
    for (int i = 1; i <= tot; ++i) {
        e[now][i].z = ct[e[now][i].id];
        c[e[now][i].id] = i;
        f[i] = e[now][i];
    }
    if (l == r) {
        ans[l] = sum;
        Clear(tot);
        sort(f + 1, f + tot + 1);
        for (int i = 1; i <= tot; ++i) {
            int x = get(f[i].x), y = get(f[i].y);
            if (x == y) continue;
            ans[l] += f[i].z;
            fa[x] = y;
        }
        return;
    }
    Clear(tot);
    for (int i = l; i <= r; ++i) f[c[a[i]]].z = -INF;
    sort(f + 1, f + tot + 1);
    int tt = 0;
    for (int i = 1; i <= tot; ++i) {
        int x = get(f[i].x), y = get(f[i].y);
        if (x == y) continue;
        fa[x] = y;
        if (f[i].z != -INF) {
            g[++tt] = f[i];
            sum += f[i].z;
        }
    }
    Clear(tot);
    for (int i = 1; i <= tt; ++i) fa[get(g[i].x)] = get(g[i].y); //缩点 
    tt = 0;
    for (int i = 1; i <= tot; ++i) {
        int x = get(f[i].x), y = get(f[i].y);
        if (x == y) continue;
        f[++tt].x = x;
        f[tt].y = y;
        f[tt].z = f[i].z;
        f[tt].id = f[i].id;
    }
    tot = tt;
    for (int i = 1; i <= tot; ++i) c[f[i].id] = i;
    for (int i = l; i <= r; ++i) f[c[a[i]]].z = INF;
    Clear(tot);
    sort(f + 1, f + tot + 1);
    tt = 0;
    for (int i = 1; i <= tot; ++i) {
        if (f[i].z == INF) {
            f[++tt] = f[i];
            continue;
        }
        int x = get(f[i].x), y = get(f[i].y);
        if (x == y) continue;
        fa[x] = y;
        f[++tt] = f[i];
    }
    tot = tt;
    for (int i = 1; i <= tot; ++i) e[now + 1][i] = f[i];//方便递归到下一层时取边用。由于下一层递归不会影响到 now + 1，故没有问题。 
    int mid(l + r >> 1); 
    CDQ(l, mid, now + 1, tot, sum);
    CDQ(mid + 1, r, now + 1, tot, sum);
}
int main() { 
    scanf("%d%d%d", &n, &m, &qq);
    for (int i = 1; i <= m; ++i) {  
        scanf("%d%d%d", &e[0][i].x, &e[0][i].y, &e[0][i].z);
        e[0][i].id = i;
        ct[i] = e[0][i].z;
    }
    for (int i = 1; i <= qq; ++i) scanf("%d%d", a + i, b + i);
    CDQ(1, qq, 0, m, 0);
    for (int i = 1; i <= qq; ++i) printf("%lld\n", ans[i]);
}