分析
对修改时间分治,假设当前的时间区间是 $[L,R]$。
考虑以下两种操作:
-
把 $[L,R]$ 中要修改的所有边修改成 $-\infty$,然后求一遍最小生成树。
发现,如果一条非 $-\infty$ 边在最小生成树中,那它以后一定也在最小生成树中,所以可以把它先加进去。于是可以把所有这样的边形成的连通块缩成一个点。
-
把 $[L,R]$ 中要修改的所有边修改为$\infty$,然后求一遍最小生成树。
发现,如果一条非 $\infty$ 边不在最小生成树中,那它以后也一定不在最小生成树中,所以可以把它删去。
这样子就可以把点数和边数都缩成 $\mathcal{O}(R - L + 1)$ 级别。于是时间复杂度满足递归式 $\mathcal{T}(n) = 2\mathcal{T}(n/2) + \mathcal{O}(n \log n)$,由主定理得时间复杂度为 $\mathcal{O}(n log^2 n)$。
当 $L=R$ 时,直接修改边权,然后求一遍最小生成树并计入答案即可。
代码
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=50000+10;
const int INF=0x3f3f3f3f;
int n,m,q;
struct Edge { int u,v,w,id; } e[30][N],d[N],t[N];
bool operator <(const Edge a,const Edge b) { return a.w<b.w; }
struct Modify { int k,d; } p[N];
int w[N],pos[N],sum[30];
ll ans[N];
int root[N];
inline int find(int x) { return x==root[x]?x:root[x]=find(root[x]); }
inline void clear(int s,Edge* e) {
for (re int i=1;i<=s;++i)
root[e[i].u]=e[i].u,root[e[i].v]=e[i].v;
}
inline void contraction(int& s,ll& val) {
int top=0; clear(s,d); sort(d+1,d+s+1);
for (re int i=1;i<=s;++i) {
int p=find(d[i].u),q=find(d[i].v);
if (p!=q) root[p]=q,t[++top]=d[i];
}
clear(top,t);
for (re int i=1;i<=top;++i) {
int p=find(t[i].u),q=find(t[i].v);
if (t[i].w!=-INF&&p!=q) val+=t[i].w,root[p]=q;
}
top=0;
for (re int i=1;i<=s;++i) {
int p=find(d[i].u),q=find(d[i].v);
if (p!=q) t[++top]=(Edge){p,q,d[i].w,d[i].id};
}
for (re int i=1;i<=top;++i) pos[d[i].id]=i,d[i]=t[i];
s=top;
}
inline void reduction(int& s) {
int top=0; clear(s,d); sort(d+1,d+s+1);
for (re int i=1;i<=s;++i) {
int p=find(d[i].u),q=find(d[i].v);
if (p!=q) t[++top]=d[i],root[p]=q;
else if (d[i].w==INF) t[++top]=d[i];
}
for (re int i=1;i<=top;++i) pos[d[i].id]=i,d[i]=t[i];
s=top;
}
inline void CDQ(int L,int R,int dep,ll val) {
if (L==R) w[p[L].k]=p[L].d; //修改
for (re int i=1;i<=sum[dep];++i) {
e[dep][i].w=w[e[dep][i].id];
d[i]=e[dep][i],pos[d[i].id]=i;
}
if (L==R) {
ans[L]=val; clear(sum[dep],d); sort(d+1,d+sum[dep]+1);
for (re int i=1;i<=sum[dep];++i) {
int p=find(d[i].u),q=find(d[i].v);
if (p!=q) root[p]=q,ans[L]+=d[i].w;
}
return;
}
int s=sum[dep];
for (re int i=L;i<=R;++i) d[pos[p[i].k]].w=-INF;
contraction(s,val);
for (re int i=L;i<=R;++i) d[pos[p[i].k]].w=INF;
reduction(s);
for (re int i=1;i<=s;++i) e[dep+1][i]=d[i];
sum[dep+1]=s;
int mid=(L+R)>>1; CDQ(L,mid,dep+1,val),CDQ(mid+1,R,dep+1,val);
}
int main() {
n=read(),m=read(),q=read();
for (re int i=1;i<=m;++i)
e[0][i].u=read(),e[0][i].v=read(),e[0][i].w=w[i]=read(),e[0][i].id=i;
for (re int i=1;i<=q;++i) p[i].k=read(),p[i].d=read();
sum[0]=m; CDQ(1,q,0,0);
for (re int i=1;i<=q;++i) printf("%lld\n",ans[i]);
return 0;
}
3 条评论
%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%这都会
您 假 死 了