【Luogu】 P3206 [HNOI2010] 城市建设

本文主要是介绍【Luogu】 P3206 [HNOI2010] 城市建设，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

点击打开链接

题目解法

动态 $m s t$ 板板题~

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

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

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

#include <bits/stdc++.h>
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;
}