P3206 [HNOI2010]城市建设

神仙题

动态带修最小生成树...

做法一

如果我们修改后的代价一定变劣,那么可以倒着做,你会发现如果我们把最小生成树上的边变优了就不会变,如果把其他边变优了就LCT维护一下

然后不能AC,有40QAQAQAQ

做法二

考虑线段树分治...

之前我们的线段树分治只用了个并查集,显得愚蠢,这里我们可以用LCT了.....

考虑回溯,我们只需要把这个线段树点带来的新边删掉,然后把由于这个点引入新边而删掉的边再搞回去,当然我们还是要Kruscal重构树啦

然后?回溯能解决那么线段树分治就做完了...复杂度是 $O(mlog^2n)$ 的,会T

做法三

CDQ老大爷终于出来了

对时间分治,然而分治的核心在于减小问题规模,咋减小啊?

引入新概念,必选边和无用边

必选边是我们已知到这个时间点,无论再向下搜到哪个时间这些边都一定要加入的

也就是说,我们这些点是维护连通性而存在的...

所以我们除开分治区间内其他边全都标成负无穷,再做最小生成树,那么还有分治区间内的边就是必选边啦

那么显然我们就可以把必选边所连接的点缩点

必选边可以用来减少点数

而无用边就是在这个时间点里也都用不上了,今后一定也用不上的边

举个经典例子:重边(或自环),~~当然没有这么简单...~~

那么无用边就是把分治区间内边标为负无穷之后再最小生成树也没有选上的边

无用边可以用来减少边数

满足了这两个做最小生成树的时间瓶颈的缩小,CDQ分治的正确性也就成立啦

时间复杂度是优美的 $O(mlogm)$

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int MAXN = 1e5 + 7;

namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = BUF_SIZE + buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		char s = nc();
		int x = 0, f = 1;
		for(; !isdigit(s); s = nc())if(s == '-')f = -1;
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x * f;
	}
}
using namespace fastIO;
int n, m, q, f[MAXN];
inline int getf(int x) {
	return f[x] == x ? x : getf(f[x]);
}
int siz[MAXN], *sz0;

struct rec {
	int u, v, w;
	inline int merge() {
		int fx = getf(u), fy = getf(v);
		if(fx == fy)return 0;
		if(sz0[fx] < sz0[fy]) {
			f[fx] = fy;
			sz0[fy] += sz0[fx];
		} else {
			f[fy] = fx;
			sz0[fx] += sz0[fy];
		}
		return 1;
	}
} e[MAXN << 1];

struct qry {
	int id, w;
} l[MAXN];


inline void bck(int x) {
	sz0[x] = siz[x];
	f[x] = x;
}
int in[MAXN], sz[MAXN], SIZ[20][MAXN], Q[20][MAXN], A[20][MAXN << 1], *a, *p;

inline int cmp(int x, int y) {
	return e[x].w < e[y].w;
}

inline void solve(int dep, int L, int R, int n, int m, int *a, int *p, ll ans) {
	register int i = 0;
	sz0 = SIZ[dep];
	for(i = 1; i <= n; ++i) {
		siz[p[i]] = sz0[p[i]];
	}
	//定这些边一定先选上
	for(i = L; i <= R; ++i) {
		e[l[i].id].merge();
	}
	for(i = 1; i <= m; ++i) {
		if(e[a[i]].merge()) {
			ans += e[a[i]].w;
			a[i] = -a[i];
			//必须选边
		}
	}
	for(i = 1; i <= n; ++i)bck(p[i]);
	int tp = 0;
	for(i = 1; i <= m; ++i) {
		if(a[i] < 0)e[-a[i]].merge();
		else a[++tp] = a[i];
	}
	m = tp;
	tp = 0;
	for(i = 1; i <= n; ++i)
		if(f[p[i]] == p[i]) {
			p[++tp] = p[i];
			siz[p[i]] = sz0[p[i]];
			//必留点
		}
	n = tp;
	tp = 0;
	//钦定这些边一定不选
	for( i = L; i <= R; ++i) {
		in[l[i].id] = 1;
	}
	for(i = 1; i <= m; ++i) {
		if(!in[a[i]] && !e[a[i]].merge())continue;
		a[++tp] = a[i];
	}
	m = tp;
	for(i = L; i <= R; ++i)in[l[i].id] = 0;
	for(i = 1; i <= n; ++i)bck(p[i]);
	if(n == 1) {
		for(i = L; i <= R; ++i) {
			e[l[i].id].w = l[i].w;
			printf("%lld\n", ans);
		}
        //只剩下一个点啦,改掉之后就计算答案吧
		return ;
	}
	if(L == R) {
		int w = e[l[L].id].w = l[L].w;
		for(i = 1; i <= m; ++i)w = min(e[a[i]].w, w);
        //显然这条边还可以康康能不能优化ans
		printf("%lld\n", ans + w);
		return ;
	}
	int mid = (L + R) >> 1;
	++dep;
	for( i = 1; i <= n; ++i)SIZ[dep][Q[dep][i] = p[i]] = sz0[p[i]];
	for( i = 1; i <= m; ++i)A[dep][i] = a[i];
	solve(dep, L, mid, n, m, A[dep], Q[dep], ans);
	--dep;
	for( i = 1; i <= n; ++i)
		f[p[i]] = p[i];
	sort(a + 1, a + m + 1, cmp);
	solve(dep, mid + 1, R, n, m, a, p, ans);
    //dep用的少
	return ;
}

int main() {
	n = read();
	m = read();
	q = read();
	for(int i = 1; i <= m; ++i) {
		e[i].u = read();
		e[i].v = read();
		e[i].w = read();
	}
	for(int i = 1; i <= q; ++i) {
		l[i].id = read();
		l[i].w = read();
	}
	for(int i = 1; i <= n; ++i)SIZ[1][i] = 1, Q[1][i] = f[i] = i;
	for(int i = 1; i <= m; ++i)A[1][i] = i;
    //栈,因为比较复杂需要回溯
	sort(A[1] + 1, A[1] + m + 1, cmp);
	solve(1, 1, q, n, m, A[1], Q[1], 0);
	return 0;
}

最后不得不说,这个真的妙啊...

夏晓光(loveJY)的博客

P5767 [NOI1997]最优乘车