BZOJ2001【HNOI2010】城市建设 < CDQ分治+MST >

Problem

【HNOI2010】城市建设

Description

是一个拥有诸多城市的大国，国王为城市的交通建设可谓绞尽脑汁。可以在某些城市之间修建道路，在不同的城市之间修建道路需要不同的花费。希望建造最少的道路使得国内所有的城市连通。但是由于某些因素，城市之间修建道路需要的花费会随着时间而改变，会不断得到某道路的修建代价改变的消息，他希望每得到一条消息后能立即知道使城市连通的最小花费总和，决定求助于你来完成这个任务。

Input

第一行三个整数，分别表示城市的数目，可以修建的道路个数，收到的消息个数。
接下来行，第行有三个用空格隔开的整数（），表示在城市与城市之间修建道路的代价为。
接下来行，每行包含两个数，表示输入的第个道路的修建代价修改为（即将修改为）。

Output

行，第行输出得知前条消息后使城市连通的最小花费总和。

Sample Input

Sample Output

1
2
3

14
10
9

HINT

对于的数据, ，，。
另有的数据，，，，且保证修改后的代价不会比之前的代价低。
对于的数据，，，。

标签：CDQ分治 MST

Solution

考虑对时间进行分治。对于分治到的每一个时间区间，确定必须存在的边并加入答案，删除一定不存在的边，再向下递归两个子区间。主要有两种操作：

：将会在该区间中被修改的边权值设为，跑，这时在最小生成树上且边权不为的边一定会存在于该区间所有时间点的最小生成树中。于是从边集中删除这些边，并将这些边连接的点合并。
：将会在该区间中被修改的边权值设为，跑，这时不在最小生成树上且边权不为的边一定不会存在于该区间所有时间点的最小生成树中。于是从边集中删除这些边即可。

和点的合并可以用并查集维护，需要维护表示编号为的点在当前边集中的位置，以实现快速更改该区间中被修改的边的权值。对每个区间进行如上两种操作，递归处理左右区间，到底部时跑统计答案即可。

Code

#include <bits/stdc++.h>
#define fir first
#define sec second
#define MAX_N 20000
#define MAX_M 50000
#define INF 0x3f3f3f3f
#define mid ((s+t)>>1)
using namespace std;
typedef long long lnt;
typedef pair<int,int> pii;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, q; lnt ans[MAX_M+5];
int fa[MAX_N+5], w[MAX_M+5], pos[MAX_M+5];
struct edge {int u, v, c, id;} ; pii qry[MAX_M+5];
bool cmp (const edge &x, const edge &y) {return x.c < y.c;}
int getf(int x) {return fa[x] == x ? x : fa[x] = getf(fa[x]);}
lnt contraction(vector <edge> &E) {
    vector <edge> e; lnt ret = 0;
    sort(E.begin(), E.end(), cmp);
    for (int i = 0, x, y; i < (int)E.size(); i++)
        if ((x = getf(E[i].u)) ^ (y = getf(E[i].v)))
            fa[y] = x, e.push_back(E[i]);
    for (int i = 0; i < (int)e.size(); i++)
        fa[e[i].u] = e[i].u, fa[e[i].v] = e[i].v;
    for (int i = 0; i < (int)e.size(); i++)
        if (e[i].c > -INF && (getf(e[i].u) ^ getf(e[i].v)))
            fa[getf(e[i].v)] = getf(e[i].u), ret += e[i].c;
    e.clear();
    for (int i = 0; i < (int)E.size(); i++)
        if (getf(E[i].u) ^ getf(E[i].v))
            pos[E[i].id] = (int)e.size(), e.push_back(E[i]), 
            e[e.size()-1].u = fa[E[i].u], e[e.size()-1].v = fa[E[i].v];
    for (int i = 0; i < (int)E.size(); i++)
        fa[E[i].u] = E[i].u, fa[E[i].v] = E[i].v;
    E = e; return ret;
}
void reduction(vector <edge> &E) {
    vector <edge> e;
    sort(E.begin(), E.end(), cmp);
    for (int i = 0, x, y; i < (int)E.size(); i++)
        if ((x = getf(E[i].u)) ^ (y = getf(E[i].v)))
            fa[y] = x, e.push_back(E[i]);
        else if (E[i].c == INF) e.push_back(E[i]);
    for (int i = 0; i < (int)E.size(); i++)
        fa[E[i].u] = E[i].u, fa[E[i].v] = E[i].v;
    E = e;
}
void bi_solve(vector <edge> E, int s, int t, lnt sum) {
    if (s == t) w[qry[s].fir] = qry[s].sec;
    for (int i = 0; i < (int)E.size(); i++)
        E[i].c = w[E[i].id], pos[E[i].id] = i;
    if (s == t) {
        sort(E.begin(), E.end(), cmp);
        for (int i = 0, x, y; i < (int)E.size(); i++)
            if ((x = getf(E[i].u)) ^ (y = getf(E[i].v)))
                fa[y] = x, sum += E[i].c;
        for (int i = 0; i < (int)E.size(); i++)
            fa[E[i].u] = E[i].u, fa[E[i].v] = E[i].v;
        ans[s] = sum; return;
    }
    for (int i = s; i <= t; i++)
        E[pos[qry[i].fir]].c = -INF;
    sum += contraction(E);
    for (int i = s; i <= t; i++)
        E[pos[qry[i].fir]].c = INF;
    reduction(E);
    bi_solve(E, s, mid, sum);
    bi_solve(E, mid+1, t, sum);
}
int main() {
    read(n), read(m), read(q); vector <edge> E;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1, u, v, c; i <= m; i++)
        read(u), read(v), read(c), w[i] = c, 
        E.push_back((edge){u, v, c, i});
    for (int i = 1; i <= q; i++)
        read(qry[i].fir), read(qry[i].sec);
    bi_solve(E, 1, q, 0);
    for (int i = 1; i <= q; i++)
        printf("%lld\n", ans[i]);
    return 0;
}