NKOJ-2936 城市建设

问题描述:

PS国是一个拥有诸多城市的大国,国王Louis为城市的交通建设可谓绞尽脑汁。
Louis可以在某些城市之间修建道路,在不同的城市之间修建道路需要不同的花费。
Louis希望建造最少的道路使得国内所有的城市连通。
但是由于某些因素,城市之间修建道路需要的花费会随着时间而改变,Louis会不断得到某道路的修建代价改变的消息,他希望每得到一条消息后能立即知道使城市连通的最小花费总和,Louis决定求助于你来完成这个任务。

输入格式:

第一行包含三个整数N,M,Q,分别表示城市的数目,可以修建的道路个数,及收到的消息个数。
接下来有M行,第i+1行有三个用空格隔开的整数Xi,Yi,Zi(1<=Xi,Yi<=N, 0<=Zi<=5*10^7),表示在城市Xi与城市Yi之间修建道路的代价为Zi。
接下来Q行,每行包含两个数k,d,表示输入的第k个道路的修建代价修改为d(即将Zi修改为d)。

输出格式:

包含Q行,第i行输出得知前i条消息后使城市连通的最小花费总和。

数据范围:

对于20%的数据, n≤1000,m≤6000,Q≤6000。
另有20%的数据,n≤1000,m≤50000,Q≤8000,修改后的代价不会比之前的代价低。
对于100%的数据, n≤20000,m≤50000,Q≤50000。

 

  一道奇奇怪怪的题,为什么会是CDQ啊(刷新认知)。但,既然ta是那ta就是吧。

 

  读完题,应该知道有最小生成树,所以现在我们知道 ta 是 MST + CDQ

  但ta的图是会变的,如果每次都跑一次 Kruskal 肯定是不行的,那怎么优化呢?

  

   因为 CDQ 所以一定是离线的,对于一个修改区间 [ L , R ] ,可以把边分为三类:

      ① 一定有用的边,即一定在 MST 上的边;

      ② 一定没有用的边,即一定不在 MST 上的边;

      ③ 不一定有用的边,即不一定在 MST 上的边。

    对于①而言,可以把相连的点缩为一个点;对于②而言,可以把无用边删去。这样缩点、删边后图的规模会越来越小。

  之后再处理  [ L , M ] 和 [ M + 1 , R ] 区间(M = ( L + R ) >> 1)。

 

  怎么实现呢?

  对于一个修改区间 [ L , R ] 的边全部设为  -inf  ,求一次MST,MST上的点是一定有用的边;对于一个修改区间 [ L , R ] 的边全部设为 inf  ,求一次MST,MST上的点是一定没用的边。

  这两点真的很好证明,读者自证不难。

  还是YY一哈,当区间 [ L , R ] 的边全部为  -inf 时,跑MST的时候,他们一定是优先选择的,如果还有其他边被选,那么这些边一定是会出现在接下来的MST中的;Vice Versa。

     

  值得注意的是:CDQ过程中,只是用来减少边数的,真正的修改边权,是在 L == R 时进行的。

 

  当然,并查集是必不可少的,要维护连通性嘛,但因为要存的数据太大了,并查集需要实现 可撤销 。具体而言,由于树深是不会超过20的,可以开20个来分别存储,即分层。

  更多细节可参考代码。

 

Code:

NKOJ-2936  城市建设
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define inf 1e9
using namespace std;
int n,m,q,Fa[50005],A[50005],B[50005],C[50005],Deep[21];
long long Ans[50005];
struct node {int x,y,z,Id;}E[21][50005],Tmp[50005],Temp[50005];
bool cmp(node a,node b) {return a.z<b.z;} 
struct nodden {int k,d;}Q[50005];
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,65536,stdin),p1==p2)?EOF:*p1++)
char buf[65536],*p1,*p2;
inline int read()
{
    char ch;int x(0);
    while((ch=gc)<48);
    do x=x*10+ch-48;while((ch=gc)>=48);
    return x;
}
inline int GetFa(int x) {return (Fa[x]==x)?x:Fa[x]=GetFa(Fa[x]);}
inline void Link(int x,int y)
{
    x=GetFa(x),y=GetFa(y);if(x==y) return;
    if(B[x]!=B[y]) (B[x]>B[y])?Fa[y]=x:Fa[x]=y;
    else Fa[x]=y,++B[y];
}
inline void Find1(int &x,long long &V)
{
    int head(0);
    for(register int i=1;i<=x;++i) Fa[Tmp[i].x]=Tmp[i].x,Fa[Tmp[i].y]=Tmp[i].y,B[Tmp[i].x]=B[Tmp[i].y]=1;
    sort(Tmp+1,Tmp+x+1,cmp);
    for(register int i=1;i<=x;++i)
        if(GetFa(Tmp[i].x)!=GetFa(Tmp[i].y)) Link(Tmp[i].x,Tmp[i].y),Temp[++head]=Tmp[i];
    for(register int i=1;i<=head;++i) Fa[Temp[i].x]=Temp[i].x,Fa[Temp[i].y]=Temp[i].y,B[Temp[i].x]=B[Temp[i].y]=1;
    for(register int i=1;i<=head;++i)
        if(Temp[i].z!=-inf&&GetFa(Temp[i].x)!=GetFa(Temp[i].y)) Link(Temp[i].x,Temp[i].y),V+=Temp[i].z;
    head=0;
    for(register int i=1;i<=x;++i)
        if(GetFa(Tmp[i].x)!=GetFa(Tmp[i].y)) Temp[++head]=node{GetFa(Tmp[i].x),GetFa(Tmp[i].y),Tmp[i].z,Tmp[i].Id}; 
    for(register int i=1;i<=head;++i) C[Tmp[i].Id]=i,Tmp[i]=Temp[i];
    x=head;
}
inline void Find2(int &x)
{
    int head(0);
    for(register int i=1;i<=x;++i) Fa[Tmp[i].x]=Tmp[i].x,Fa[Tmp[i].y]=Tmp[i].y,B[Tmp[i].x]=B[Tmp[i].y]=1;
    sort(Tmp+1,Tmp+x+1,cmp);
    for(register int i=1;i<=x;++i)
        if(GetFa(Tmp[i].x)!=GetFa(Tmp[i].y)) Link(Tmp[i].x,Tmp[i].y),Temp[++head]=Tmp[i];
        else if(Tmp[i].z==inf) Temp[++head]=Tmp[i];
    for(register int i=1;i<=head;++i) C[Tmp[i].Id]=i,Tmp[i]=Temp[i];
    x=head;
}
inline void CDQ(int L,int R,int deep,long long V)
{
    int k=Deep[deep],M=(L+R)>>1;
    if(L==R) A[Q[L].k]=Q[L].d;
    for(register int i=1;i<=k;++i) E[deep][i].z=A[E[deep][i].Id],Tmp[i]=E[deep][i],C[Tmp[i].Id]=i;
    if(L==R)
    {
        for(register int i=1;i<=k;++i) Fa[Tmp[i].x]=Tmp[i].x,Fa[Tmp[i].y]=Tmp[i].y,B[Tmp[i].x]=B[Tmp[i].y]=1;
        Ans[L]=V,sort(Tmp+1,Tmp+k+1,cmp);
        for(register int i=1;i<=k;++i)
            if(GetFa(Tmp[i].x)!=GetFa(Tmp[i].y)) Link(Tmp[i].x,Tmp[i].y),Ans[L]+=Tmp[i].z;
        return;
    }
    for(register int i=L;i<=R;++i) Tmp[C[Q[i].k]].z=-inf;
    Find1(k,V);
    for(register int i=L;i<=R;++i) Tmp[C[Q[i].k]].z=inf;
    Find2(k);
    for(register int i=1;i<=k;++i) E[deep+1][i]=Tmp[i];
    Deep[deep+1]=k,CDQ(L,M,deep+1,V),CDQ(M+1,R,deep+1,V);
}
int main()
{
    n=read(),m=read(),q=read();
    for(register int i=1;i<=m;++i) E[0][i].x=read(),E[0][i].y=read(),E[0][i].z=A[i]=read(),E[0][i].Id=i;
    for(register int i=1;i<=q;++i) Q[i].k=read(),Q[i].d=read();
    Deep[0]=m,CDQ(1,q,0,0);
    for(register int i=1;i<=q;++i) printf("%lld\n",Ans[i]);
    return 0;
}
城市建设
上一篇:F. Euclid's nightmare 题解(MST+思维)


下一篇:CF1108F MST Unification