Luogu

BZOJ

分析

极其神仙的CDQ分治(其实我觉得应该评成黑题)

这是一个经典的动态MST问题。

对修改时间分治,假设当前的时间区间是$[L,R]$。

考虑两种比较极端的情况:

  • 将边权修改为$-\infty$

把$[L,R]$中要修改的所有边修改成$-\infty$,然后求一遍最小生成树。
发现,如果一条非$-\infty$边在最小生成树中,那它以后一定也在最小生成树中,所以可以把它先加进去。
于是可以把所有这样的边形成的连通块缩成一个点,然后把答案加上。
这样子形成了一个森林,把连接每棵树的边存下来,继续分治。

  • 将边权修改为$\infty$

把$[L,R]$中要修改的所有边修改为$\infty$,然后求一遍最小生成树。
发现,如果一条非$\infty$边不在最小生成树中,那它以后也一定不在最小生成树中,所以可以把它删去。
于是可以只保存需要的边和修改的边,继续分治。

然后每一层都两种情况搞一下,就可以减小图的规模了。

边界就是$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) { //边界,求MST
        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;
}
最后修改:2019 年 09 月 24 日 10 : 12 PM