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

Posted on Symbols count in article: 1.4k Reading time ≈ 5 mins.

Problem

【HNOI2010】城市建设

Time  Limit:  20  Sec\mathrm{Time\;Limit:\;20\;Sec}
Memory  Limit:  162  MB\mathrm{Memory\;Limit:\;162\;MB}

Description

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

Input

第一行三个整数N,M,QN,M,Q，分别表示城市的数目，可以修建的道路个数，收到的消息个数。
接下来MM行，第i+1i+1行有三个用空格隔开的整数Xi,Yi,ZiX_i,Y_i,Z_i（1≤Xi,Yi≤n,0≤Zi≤5×1071\le X_i,Y_i\le n, 0\le Z_i\le5\times10^7），表示在城市XiX_i与城市YiY_i之间修建道路的代价为ZiZ_i。
接下来QQ行，每行包含两个数k,dk,d，表示输入的第kk个道路的修建代价修改为dd（即将ZkZ_k修改为dd）。

Output

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

Sample Input

1
2
3
4
5
6
7
8
9
5 5 3
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
1 6
1 1
5 3

Sample Output

1
2
3
14
10
9

HINT

对于20%20\%的数据, n≤1000n\le1000，m≤6000m\le6000，Q≤6000Q\le6000。
另有20%20\%的数据，n≤1000n\le1000，m≤50000m\le50000，Q≤8000Q\le8000，且保证修改后的代价不会比之前的代价低。
对于100%100\%的数据，n≤20000n\le20000，m≤50000m\le50000，Q≤50000Q\le50000。

标签：CDQ分治 MST

Solution

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

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

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#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;
}