Description
Link.
修改边权的动态 MST。
Solution
讲清楚点。
修改边权的 MST，考虑对时间分治。设我们当前操作的操作区间是 $[l,r]$，直接暴力找 MST 是不行的。
考虑找出必要的边和必不要的边。
- 若把 $[l,r]$ 操作中的边边权改成 $+\infty$，拿原图点集和不包含 $[l,r]$ 中边的边集和 $[l,r]$ 中边权修改为 $+\infty$ 后的边的集合的并集作为边集跑 MST，此时如果不在 MST 上的边一定不在最终的 MST 边集中。
- 同理，改成 $-\infty$，此时在 MST 边集里的边一定在最终的 MST 边集中。
这样暴力跑 Kruskal 的规模保证在了 $O(r-l+1)$。
复杂度 $O(n\log_{2}^{2}n)$。
#include<bits/stdc++.h>
const int INF=std::numeric_limits<int>::max();
struct edge
{
int fr,ba,val,ID;
edge():fr(0),ba(0),val(0),ID(0){}
edge(int _fr,int _ba,int _val,int _id):fr(_fr),ba(_ba),val(_val),ID(_id){}
friend bool operator < (const edge &lhs,const edge &rhs){return lhs.val<rhs.val;}
}edge_set[20][100010],ori_edge[100010],tmp_edge[100010];
struct oper
{
int ID,val;
oper():ID(0),val(0){}
oper(int _id,int _val):ID(_id),val(_val){}
}ope[100010];
int tagcur[100010],tagope[100010],n,m,q,size_v[20],size_e[20],ver_set[20][100010],wgt[100010],srt[100010];
struct DSU
{
int fa[100010];
int f(int i){return fa[i];}
void clear(int l){std::iota(fa+1,fa+l+1,1);}
int find(int x){return (x^fa[x])?fa[x]=find(fa[x]):x;}
bool merge(int x,int y){x=find(x),y=find(y); if(x^y) return fa[x]=y,true; else return false;}
}dsu;
int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0' || c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
if(~f) return x;
else return -x;
}
int wrstk[100];
void write(long long x,char las='\n')
{
int top=0;
if(x<0) x=-x,putchar('-');
do wrstk[++top]=x%10,x/=10; while(x);
while(top) putchar(wrstk[top--]^'0');
putchar(las);
}
void rawgrass(int l,int r,int dep,long long ans)
{
const int &n=size_v[dep],&m=size_e[dep];
if(l^r)
{
for(int i=1;i<=m;++i) tagope[edge_set[dep][i].ID]=0;
for(int i=l;i<=r;++i) tagcur[ope[i].ID]=1;
for(int i=1;i<=m;++i)
{
tmp_edge[i]=edge_set[dep][i];
if(tagcur[tmp_edge[i].ID]) tmp_edge[i].val=INF;
}
std::sort(tmp_edge+1,tmp_edge+m+1);
dsu.clear(n);
for(int i=1;i<=m;++i) if(!dsu.merge(tmp_edge[i].fr,tmp_edge[i].ba) && tmp_edge[i].val!=INF) tagope[tmp_edge[i].ID]=-1;
for(int i=l;i<=r;++i) tagcur[ope[i].ID]=1;
for(int i=1;i<=m;++i)
{
tmp_edge[i]=edge_set[dep][i];
if(tagcur[tmp_edge[i].ID]) tmp_edge[i].val=-INF;
}
std::sort(tmp_edge+1,tmp_edge+m+1);
dsu.clear(n);
for(int i=1;i<=m;++i) if(dsu.merge(tmp_edge[i].fr,tmp_edge[i].ba) && tmp_edge[i].val!=-INF) tagope[tmp_edge[i].ID]=1;
for(int i=l;i<=r;++i) tagcur[ope[i].ID]=0;
size_v[dep+1]=size_e[dep+1]=0;
dsu.clear(n);
for(int i=1;i<=m;++i) if(tagope[edge_set[dep][i].ID]==1) dsu.merge(edge_set[dep][i].fr,edge_set[dep][i].ba);
for(int i=1;i<=n;++i) if(dsu.f(i)==i) ver_set[dep+1][++size_v[dep+1]]=ver_set[dep][i],srt[i]=size_v[dep+1];
for(int i=1;i<=m;++i)
{
if(tagope[edge_set[dep][i].ID]==1) ans+=edge_set[dep][i].val;
else if(tagope[edge_set[dep][i].ID]==0)
{
int x=edge_set[dep][i].fr,y=edge_set[dep][i].ba;
x=dsu.find(x),y=dsu.find(y);
if(x^y) edge_set[dep+1][++size_e[dep+1]]=edge(srt[x],srt[y],edge_set[dep][i].val,edge_set[dep][i].ID);
}
}
int mid=(l+r)>>1;
rawgrass(l,mid,dep+1,ans);
for(int i=l;i<=mid;++i) wgt[ope[i].ID]=ope[i].val;
for(int i=1;i<=size_e[dep+1];++i) if(wgt[edge_set[dep+1][i].ID]!=INF) edge_set[dep+1][i].val=wgt[edge_set[dep+1][i].ID];
for(int i=l;i<=mid;++i) wgt[ope[i].ID]=INF;
rawgrass(mid+1,r,dep+1,ans);
}
else
{
for(int i=1;i<=m;++i)
{
tmp_edge[i]=edge_set[dep][i];
if(tmp_edge[i].ID==ope[l].ID) tmp_edge[i].val=ope[l].val;
}
std::sort(tmp_edge+1,tmp_edge+m+1);
dsu.clear(n);
for(int i=1;i<=m;++i) if(dsu.merge(tmp_edge[i].fr,tmp_edge[i].ba)) ans+=tmp_edge[i].val;
write(ans);
}
}
int main()
{
n=read(),m=read(),q=read();
for(int i=1,x,y,z;i<=m;++i) x=read(),y=read(),z=read(),ori_edge[i]=edge(x,y,z,i);
for(int i=1,id,k;i<=q;++i) id=read(),k=read(),ope[i]=oper(id,k);
size_v[0]=n;
size_e[0]=m;
for(int i=1;i<=size_v[0];++i) ver_set[0][i]=i;
for(int i=1;i<=size_e[0];++i) edge_set[0][i]=ori_edge[i],wgt[i]=INF;
rawgrass(1,q,0,0);
return 0;
}