BZOJ 2001 - [Hnoi2010]City 城市建设

#最小生成树 #CDQ分治
Published on 2016-05-29

题目地址

描述

有一个 n(n≤20000)n(n\le 20000) 个点 m(m≤50000)m(m \le 50000) 边的无向图，每条边有边权 WiW_i，给定 Q(Q≤50000)Q(Q\le 50000) 个操作 (Ei,Zi)(E_i,Z_i)，表示将第 EiE_i 条边的费用改为 ZiZ_i，每次操作之后，输出当前无向图的最小生成树权值。

分析

这个问题是不能用一般的 LCT 求解的，为什么呢？因为边权有增有减，相当于不断的加边删边，两种操作都有就没办法了。
事实上，这是一个论文题，在 WC2013 上面讲过。

PPT1
WC2013

由于分治的重要思想在于每次分治的复杂度必须与当前区间长度有关，其本解法的核心思想在于，每次分治的过程中，通过确定无用的边来将边数下降到当前区间长度的级别，通过确定必要的边再缩点来将点数下降到当前区间长度的级别。最后分治到边界的时候使这次的修改生效，并做一次最小生成树。这样每次分治的复杂度都是 O(nlogn)O(n\log n)，所以总的复杂度只是 O(nlog2n)O(n\log^2 n)。

实现技巧方面采用了分层建图，MAP 函数，撤销并查集（其实就是暴力初始化）等技巧，建议仔细研读（我也是从 miskcoo 那儿学来的）。

代码

//  Created by Sengxian on 5/28/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 2001 CDQ 动态维护生成树
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 20000 + 3, maxm = 50000 + 3, maxq = maxm, maxLevel = 16;

struct edge {
    int from, to, cost, id;
    edge(int from = 0, int to = 0, int cost = 0, int id = 0): from(from), to(to), cost(cost), id(id) {}
    inline bool operator < (const edge &ano) const {return cost < ano.cost;}
}edges[maxLevel][maxm], d[maxm], t[maxm]; // 存下每一层的图，方便操作

struct query {
    int id, cost;
}ques[maxq];

namespace unionset {
    int fa[maxn];
    void init(int n) {
        for (int i = 0; i < n; ++i) fa[i] = i;
    }
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        fa[x] = y;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
}
using namespace unionset;

int n, m, q, weight[maxm], emap[maxm];
ll ans[maxq];

//恢复并查集
void reset(int n, edge *d) {
    for (int i = 0; i < n; ++i) {
        fa[d[i].from] = d[i].from;
        fa[d[i].to] = d[i].to;
    }
}


ll contraction(int &n) {
    int tmp = 0;
    sort(d, d + n);
    //找出必须要的非 -INF 边
    for (int i = 0; i < n; ++i)
        if (!same(d[i].from, d[i].to)) {
            unite(d[i].from, d[i].to);
            t[tmp++] = d[i];
        }

    reset(tmp, t);
    ll v = 0;
    //这些边必须要，合成一个联通分量来缩点
    for (int i = 0; i < tmp; ++i)
        if (t[i].cost != INT_MIN && !same(t[i].from, t[i].to)) {
            unite(t[i].from, t[i].to);
            v += t[i].cost;
        }

    tmp = 0; //开始缩点
    for (int i = 0; i != n; ++i)
        if (!same(d[i].from, d[i].to)) {
            t[tmp] = d[i];
            t[tmp].from = find(d[i].from); //剩下 -INF 的边的两端变为缩点后的点
            t[tmp].to = find(d[i].to);
            emap[d[i].id] = tmp++;
        }

    reset(n, d);
    n = tmp;
    for (int i = 0; i < tmp; ++i) d[i] = t[i];
    return v;
}

void reduction(int &n) {
    int tmp = 0;
    sort(d, d + n);
    for (int i = 0; i < n; ++i)
        if (!same(d[i].from, d[i].to)) {
            unite(d[i].from, d[i].to);
            t[tmp] = d[i];
            emap[d[i].id] = tmp++;
        } else if (d[i].cost == INT_MAX) {
            t[tmp] = d[i];
            emap[d[i].id] = tmp++;
        }
    reset(n, d);
    n = tmp;
    for (int i = 0; i < n; ++i) d[i] = t[i];
}

//[l, r) 询问区间，level 当前层数，当前边数，当前已经钦点的边的 cost 和
void solve(int l, int r, int level, int n, ll v) {
    if (r - l == 1) weight[ques[l].id] = ques[l].cost; //让修改生效，但 edges 的边权可能都是乱的，所以改的是 weight

    for (int i = 0; i < n; ++i) {
        edges[level][i].cost = weight[edges[level][i].id]; //恢复边权
        d[i] = edges[level][i]; //d 临时储存边，用它来进行 C & R 
        emap[edges[level][i].id] = i; //得到位置
    }

    if (r - l == 1) {
        ans[l] = v;
        sort(d, d + n);
        for (int i = 0; i < n; ++i)
            if (!same(d[i].from, d[i].to)) {
                unite(d[i].from, d[i].to);
                ans[l] += d[i].cost;
            }
        return reset(n, d);
    }

    //根据定理，钦点一些边，合并联通分量
    for (int i = l; i < r; ++i)
        d[emap[ques[i].id]].cost = INT_MIN;
    v += contraction(n);

    //根据定理，删除不需要的边
    for (int i = l; i < r; ++i)
        d[emap[ques[i].id]].cost = INT_MAX;
    reduction(n);

    for (int i = 0; i < n; ++i)
        edges[level + 1][i] = d[i];

    int mid = (l + r) / 2;
    solve(l, mid, level + 1, n, v);
    solve(mid, r, level + 1, n, v);
}



int main() {
    n = ReadInt(), m = ReadInt(), q = ReadInt();
    for (int i = 0; i < m; ++i) {
        edges[0][i].from = ReadInt() - 1, edges[0][i].to = ReadInt() - 1, edges[0][i].cost = ReadInt();
        edges[0][i].id = i; //weight 记录每条边当前的权重
        weight[i] = edges[0][i].cost;
    }
    for (int i = 0; i < q; ++i)
        ques[i].id = ReadInt() - 1, ques[i].cost = ReadInt();

    init(n);
    solve(0, q, 0, m, 0);

    for (int i = 0; i < q; ++i)
        printf("%lld\n", ans[i]);
    return 0;
}
BZOJ 4105 - [Thu Summer Camp 2015]平方运算