【Luogu】 P3206 [HNOI2010] 城市建设

题目链接

点击打开链接

题目解法

动态 $mst$ 板板题~

考虑类似于线段树分治的做法
我们需要把边划分成静态边和动态边
动态边是当前分治区间 $[l,r]$ 中修改的边，其他边是静态边
我们考虑到静态边的边集太大，考虑缩小范围，不难想到 答案加上必选边 和 删去无用边

1. 令动态边的边权为 $-\infty$，这样仍在 $mst$ 中的边就是必选边（在区间 $[l,r]$ 中的任何一个子区间都是）
2. 令动态边的边权为 $+\infty$，这样不在 $mst$ 中的边就是无用边（在区间 $[l,r]$ 中的任何一个子区间都是）

对于必选边，我们需要把它们缩点
然后不要忘记把除了删边其他的 $u,v$ 全部改成缩点之后的集合
我们提前加上必选边的贡献，且删去无用边之后，不难发现，静态边的个数是 $O(r-l+1)$ 级别的
且有一个非常重要的性质是，我们在分治树上一层一层往下递归时，静态边是递减的，这样可以缩小问题规模
最后当 $l=r$ 时，做一遍 $mst$ 即可
时间复杂度 $O(qlogm)$

#include 
using namespace std;
typedef long long LL;
const int N=20100,M=50100,inf=1e9;
struct Lines{ int x,y,z,id;}e[20][M],f[M],tmp[M],t[M];
struct Updt{ int x,d;}upd[M];
int n,m,q,c[M],fa[N],rv[M],totE[20];
LL ans[M];
inline int read(){
	int FF=0,RR=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
	for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
	return FF*RR;
}
void _clear(int curE){ for(int i=1;i<=curE;i++) fa[f[i].x]=f[i].x,fa[f[i].y]=f[i].y;}
void _sort(int curE){ sort(f+1,f+curE+1,[](const Lines &i,const Lines &j){ return i.z<j.z;});}
int get_father(int x){ return x==fa[x]?x:fa[x]=get_father(fa[x]);}
void slv1(int &curE,LL &mst){
	_sort(curE),_clear(curE);
	int cnt=0;
	for(int i=1;i<=curE;i++){
		int fax=get_father(f[i].x),fay=get_father(f[i].y);
		if(fax!=fay) fa[fax]=fay,t[++cnt]=f[i];
	}
    _clear(curE);
    for(int i=1;i<=cnt;i++) if(t[i].z!=-inf) mst+=t[i].z,fa[get_father(t[i].x)]=get_father(t[i].y);
    int sz=0;
    for(int i=1;i<=curE;i++){
        int fax=get_father(f[i].x),fay=get_father(f[i].y);
        if(fax!=fay) f[i].x=fax,f[i].y=fay,tmp[++sz]=f[i];
    }
	for(int i=1;i<=sz;i++) f[i]=tmp[i],rv[f[i].id]=i;
    curE=sz;
}
void slv2(int &curE){
	_sort(curE),_clear(curE);
	int sz=0;
	for(int i=1;i<=curE;i++){
		int fax=get_father(f[i].x),fay=get_father(f[i].y);
		if(fax!=fay) fa[fax]=fay,tmp[++sz]=f[i];
		else if(f[i].z==inf) tmp[++sz]=f[i];
	}
	for(int i=1;i<=sz;i++) f[i]=tmp[i],rv[f[i].id]=i;
    curE=sz;
}
void solve(int l,int r,int depth,LL mst){
	int curE=totE[depth];
	if(l==r) c[upd[l].x]=upd[l].d;
	for(int i=1;i<=curE;i++){
		e[depth][i].z=c[e[depth][i].id];
		f[i]=e[depth][i],rv[f[i].id]=i;
	}
	if(l==r){
		ans[l]=mst;
		_sort(curE),_clear(curE);
		for(int i=1;i<=curE;i++){
			int fax=get_father(f[i].x),fay=get_father(f[i].y);
			if(fax!=fay) fa[fax]=fay,ans[l]+=f[i].z;
		}
		return;
	}
	for(int i=l;i<=r;i++) f[rv[upd[i].x]].z=-inf;
	slv1(curE,mst);
	for(int i=l;i<=r;i++) f[rv[upd[i].x]].z=inf;
	slv2(curE);
	for(int i=1;i<=curE;i++) e[depth+1][i]=f[i];
	totE[depth+1]=curE;
	int mid=(l+r)>>1;
	solve(l,mid,depth+1,mst),solve(mid+1,r,depth+1,mst);
}
int main(){
	n=read(),m=read(),q=read();
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),z=read();
		e[0][i]={x,y,z,i},c[i]=z;
	}
	for(int i=1;i<=q;i++) upd[i].x=read(),upd[i].d=read();
	totE[0]=m,solve(1,q,0,0);
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
	fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
	return 0;
}

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