2001: [Hnoi2010]City 城市建设
Time Limit: 20 Sec Memory Limit: 162 MB
Submit: 1132 Solved: 555
[Submit][Status][Discuss]
Description
PS国是一个拥有诸多城市的大国，国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路，在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素，城市之间修建道路需要的花费会随着时间而改变，Louis会不断得到某道路的修建代价改变的消息，他希望每得到一条消息后能立即知道使城市连通的最小花费总和， Louis决定求助于你来完成这个任务。
Input
文件第一行包含三个整数N,M,Q，分别表示城市的数目，可以修建的道路个数，及收到的消息个数。 接下来M行，第i+1行有三个用空格隔开的整数Xi,Yi,Zi(1≤Xi,Yi≤n, 0≤Zi≤50000000)，表示在城市Xi与城市Yi之间修建道路的代价为Zi。接下来Q行，每行包含两个数k,d，表示输入的第k个道路的修建代价修改为d(即将Zk修改为d)。
Output
输出包含Q行，第i行输出得知前i条消息后使城市连通的最小花费总和。
Sample Input
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
1 6
1 1
5 3
Sample Output
10
9
HINT
【数据规模】 对于20%的数据, n≤1000,m≤6000,Q≤6000。 有20%的数据，n≤1000,m≤50000,Q≤8000,修改后的代价不会比之前的代价低。 对于100%的数据, n≤20000,m≤50000,Q≤50000。
Source
十分懵逼的一道CDQ分治。
solve(l,r) 解决l到r区间内的修改及询问。
边界：l==r，可以直接做最小生成树得到答案。
其他：递归之前，需要在当前层进行两个操作：
contraction 求出所有的必须边，并直接把必须边加入答案，之后不再考虑；顺道把必须边连接的两点永久合并。
reduction 求出所有的不可能边，并直接把不可能边删除，之后不再考虑。
把所有待修改的边权值设为-inf，做最小生成树，在MST上的非待修改边都是必须边。
把所有待修改的边权值设为+inf，做最小生成树，不在MST上的非待修改边都是不可能边。
进行两个操作之后，图的规模会缩小，也许是缩小一半，不造，这个太玄学，大爷都不会。
#include <bits/stdc++.h>
inline int getC(void) {
static const int siz = ;
static char buf[siz];
static char *hd = buf + siz;
static char *tl = buf + siz;
if (hd == tl)
fread(hd = buf, , siz, stdin);
return int(*hd++);
}
inline int getI(void) {
register int ret = ;
register int neg = false;
register int bit = getC();
for (; bit < ; bit = getC())
if (bit == '-')neg ^= true;
for (; bit > ; bit = getC())
ret = ret * + bit - '';
return neg ? -ret : ret;
}
typedef long long lnt;
const int inf = 1e9;
const int maxn = ;
const int maxm = ;
int N, M, Q;
int a[maxm];
int c[maxm];
int sum[maxn];
lnt ans[maxm];
struct edge {
int x, y, w, p;
inline friend bool operator <
(const edge &a, const edge &b) {
return a.w < b.w;
}
}e[][maxm], d[maxm], b[maxm];
struct edit {
int x, y;
}q[maxm];
int fa[maxn];
int find(int u) {
return fa[u] == u ? u : fa[u] = find(fa[u]);
}
inline void clear(int t) {
for (int i = ; i <= t; ++i)
fa[d[i].x] = d[i].x,
fa[d[i].y] = d[i].y;
}
inline void merge(int x, int y) {
fa[y] = x;
}
inline void contraction(int &t, lnt &cnt) {
clear(t); int tmp = ;
std::sort(d + , d + + t);
for (int i = ; i <= t; ++i)
if (find(d[i].x) != find(d[i].y))
merge(find(d[i].x), find(d[i].y)), b[++tmp] = d[i];
for (int i = ; i <= tmp; ++i)
fa[b[i].x] = b[i].x,
fa[b[i].y] = b[i].y;
for (int i = ; i <= tmp; ++i)
if (b[i].w != -inf && find(b[i].x) != find(b[i].y))
merge(find(b[i].x), find(b[i].y)), cnt += b[i].w;
tmp = ;
for (int i = ; i <= t; ++i)
if (find(d[i].x) != find(d[i].y)) {
b[++tmp] = d[i];
c[d[i].p] = tmp;
b[tmp].x = find(d[i].x);
b[tmp].y = find(d[i].y);
}
for (int i = ; i <= tmp; ++i)d[i] = b[i];
t = tmp;
}
inline void reduction(int &t) {
clear(t); int tmp = ;
std::sort(d + , d + + t);
for (int i = ; i <= t; ++i)
if (find(d[i].x) != find(d[i].y)) {
merge(find(d[i].x), find(d[i].y));
b[++tmp] = d[i];
c[d[i].p] = tmp;
}
else if (d[i].w == inf) {
b[++tmp] = d[i];
c[d[i].p] = tmp;
}
for (int i = ; i <= tmp; ++i)d[i] = b[i];
t = tmp;
}
void solve(int l, int r, int now, lnt cnt) {
int t = sum[now];
if (l == r)a[q[l].x] = q[l].y;
for (int i = ; i <= t; ++i)
e[now][i].w = a[e[now][i].p];
for (int i = ; i <= t; ++i)
d[i] = e[now][i], c[d[i].p] = i;
if (l == r) {
ans[l] = cnt; clear(t);
std::sort(d + , d + + t);
for (int i = ; i <= t; ++i)
if (find(d[i].x) != find(d[i].y))
merge(find(d[i].x), find(d[i].y)), ans[l] += d[i].w;
return;
}
for (int i = l; i <= r; ++i)
d[c[q[i].x]].w = -inf;
contraction(t, cnt);
for (int i = l; i <= r; ++i)
d[c[q[i].x]].w = inf;
reduction(t);
for (int i = ; i <= t; ++i)
e[now + ][i] = d[i];
sum[now + ] = t;
int mid = (l + r) >> ;
solve(l, mid, now + , cnt);
solve(mid + , r, now + , cnt);
}
signed main(void) {
N = getI();
M = getI();
Q = getI();
for (int i = ; i <= M; ++i) {
e[][i].p = i;
e[][i].x = getI();
e[][i].y = getI();
e[][i].w = getI();
a[i] = e[][i].w;
}
for (int i = ; i <= Q; ++i) {
q[i].x = getI();
q[i].y = getI();
}
sum[] = M;
solve(, Q, , );
for (int i = ; i <= Q; ++i)
printf("%lld\n", ans[i]);
}
@Author: YouSiki