Rockdu's Blog

【题目描述】

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

【输入】

文件第一行包含三个整数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)。

【输出】

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

【输入样例】

5 5 3
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
1 6
1 1
5 3

【输出样例】

14
10
9

【提示】

【数据规模】 对于20%的数据, n≤1000,m≤6000,Q≤6000。 有20%的数据，n≤1000,m≤50000,Q≤8000,修改后的代价不会比之前的代价低。 对于100%的数据, n≤20000,m≤50000,Q≤50000。

做完本题可以说开启了cdq分治的全新版本。它提供了分治的另一个方向：分而不治。这道题的精华就在于它的分治并不是在处理问题，而是在缩小问题规模。具体的来说，就是在每一层分治下缩小图的规模。

考虑每一层分治进行两个操作：

1、删除一定不会选择的边：考虑把当前区间内所有要修改的边权值赋值为inf，此时做一遍最小生成树，可以知道这时候不在最小生成树内的非修改边一定是不会选择的，这些边以后也一定不会选择，因此可以删掉。

2、选定一些一定会选的边：考虑把当前区间内所有要修改的边权值赋值为-inf，此时做一遍最小生成树，可以知道这时候在最小生成树内的非-inf边是一定要选的，我们选择这些边，再用选定的边组成的联通快缩点传给下一层。

#include<cstdio>
#include<stack>
#include<cstring>
#include<algorithm>
#define LL long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 1e5 + 5, inf = 0x3f3f3f3f;
int nds[21], eds[21], w[maxn];
int n, m, q;
struct edge {
	int u, v, w, ord, next, chs;
}e[21][maxn];
struct Qs {
	int id, w;
} Q[maxn];
edge GRP[maxn];

bool cmp_w(const edge &A, const edge &B) {
	return A.w < B.w;
}

namespace DSU {
	int fa[maxn];
	void init(int n) {For(i, 1, n) fa[i] = i;}
	int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
	int combine(int x, int y) {
		x = find(x), y = find(y);
		if(x == y) return 0;
		return fa[x] = y;
	}
}

int cont[maxn], tp, vis[maxn], oid[maxn];

void Shrink(int now, int n, int & m) {
	int cnt = 0;
	DSU::init(n);
	sort(GRP + 1, GRP + m + 1, cmp_w);
	For(i, 1, m) {
		if(DSU::combine(GRP[i].u, GRP[i].v)) 
		GRP[i].chs = 1, ++cnt;
		if(cnt == n - 1) break;
	}
	cnt = 0;
	For(i, 1, m)
		if(!(!GRP[i].chs && GRP[i].w != inf))
			GRP[++cnt] = GRP[i], GRP[cnt].chs = 0, oid[GRP[cnt].ord] = cnt;
	m = cnt;
}

LL Lock(int now, int & n, int & m) {
	int cnt = 0, tmp, ru, rv; LL ans = 0;
	int tp = 0; DSU::init(n);
	sort(GRP + 1, GRP + m + 1, cmp_w);
	For(i, 1, m) {
		if(DSU::combine(GRP[i].u, GRP[i].v)) 
		GRP[i].chs = 1, ++tp;
		if(tp == n - 1) break;
	}
	tp = 0, DSU::init(n);
	For(i, 1, m)
		if(GRP[i].chs && GRP[i].w != -inf)
			if(DSU::combine(GRP[i].u, GRP[i].v))
				ans += GRP[i].w;
	For(i, 1, n) if(!vis[tmp = DSU::find(i)]) 
		vis[tmp] = 1, cont[tmp] = ++tp;
	n = tp, tp = 0;
	For(i, 1, m) {
		ru = cont[DSU::find(GRP[i].u)];
		rv = cont[DSU::find(GRP[i].v)];
		oid[GRP[i].ord] = 0;
		vis[GRP[i].u] = vis[GRP[i].v] = 0;
		if(ru == rv) continue;
		GRP[++tp] = GRP[i], GRP[tp].chs = 0;
		GRP[tp].u = ru, GRP[tp].v = rv;
		oid[GRP[tp].ord] = tp;
	}
	return m = tp, ans;
}

LL ans[maxn];
void cdq(int l, int r, int now, LL tmp) {
	int n = nds[now], m = eds[now];
	if(l == r) w[Q[l].id] = Q[l].w;
	For(i, 1, m) e[now][i].w = w[e[now][i].ord];
	For(i, 1, m) GRP[i] = e[now][i], oid[GRP[i].ord] = i;
	if(l == r) {
		sort(GRP + 1, GRP + m + 1, cmp_w), DSU::init(n);
		For(i, 1, m) if(DSU::combine(GRP[i].u, GRP[i].v)) 
			ans[l] += GRP[i].w;
		ans[l] += tmp;
		return ;
	}
	For(i, l, r) GRP[oid[Q[i].id]].w = inf;
	Shrink(now, n, m);
	For(i, l, r) GRP[oid[Q[i].id]].w = -inf;
	tmp += Lock(now, n, m);
	For(i, 1, m) e[now + 1][i] = GRP[i];
	nds[now + 1] = n, eds[now + 1] = m;
	int mid = l + r >> 1;
	cdq(l, mid, now + 1, tmp);
	cdq(mid + 1, r, now + 1, tmp);
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	For(i, 1, m) scanf("%d%d%d", &e[0][i].u, &e[0][i].v, &w[i]), e[0][i].ord = i;
	For(i, 1, q) scanf("%d%d", &Q[i].id, &Q[i].w);
	nds[0] = n, eds[0] = m, cdq(1, q, 0, 0);
	For(i, 1, q) printf("%lld\n", ans[i]);
	return 0;
}