bzoj 2594

很好的一道LCT题目

首先我们可以发现，题目要求的就是最小生成树上的一条树链的最长边的长度，因此我们实际只需动态维护最小生成树即可

然后我们考虑怎么动态维护最小生成树

不难发现，如果涉及在最小生成树上删边，那么这个操作将变得非常复杂，因为我们并不知道删边之后要把什么样的边补充回去才行

但是，如果我们倒序操作，把删边变成加边，那么这个操作就变得相对简单了

回到本题，首先，我们把一定不会删的边建成一棵最小生成树（或者一个森林？）,这就是我们的初始状态

然后，倒序操作，每次把删边变为加边，这样每次加入一条边时，我们只需讨论这两个点原先是否联通即可

如果两个点原先就联通，那么我们就找到这两个点所在联通块里边权最大的边，删去那条边之后加入这条新来的边即可

但是LCT难以维护边权，因此我们对每条边虚拟一个有点权的点，加边时把边的两个端点连到这个点上即可

删边同理

注意维护边的编号

贴代码：

（这个东西由于常数过于巨大在bzoj上过不去，但是luogu上的数据减弱版能过）

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#include <map>

using namespace std;

struct Ques

{

    int x,y,typ,num;

}q[1000005];

struct Edge

{

    int l,r,v;

    friend bool operator < (Edge a,Edge b)

    {

        return a.v<b.v;

    }

}edge[1000005];

map <pair<int,int>,int> M;

int n,m,Q;

int ch[2000005][2];

int vis[2000005];

int maxx[2000005];

int val[2000005];

int f[2000005];

int fl[2000005];

int ret[2000005];

void update(int x)

{

    maxx[x]=val[x];

    if(edge[maxx[ch[x][0]]].v>edge[maxx[x]].v)maxx[x]=maxx[ch[x][0]];

    if(edge[maxx[ch[x][1]]].v>edge[maxx[x]].v)maxx[x]=maxx[ch[x][1]];

}

bool be_root(int x)

{

    if(ch[f[x]][0]==x||ch[f[x]][1]==x)return 0;

    return 1;

}

void pushdown(int x)

{

    if(fl[x])

    {

        swap(ch[ch[x][0]][0],ch[ch[x][0]][1]);

        swap(ch[ch[x][1]][0],ch[ch[x][1]][1]);

        fl[ch[x][0]]^=1,fl[ch[x][1]]^=1;

        fl[x]=0;

    }

}

void repush(int x)

{

    if(!be_root(x))repush(f[x]);

    pushdown(x);

}

void rotate(int x)

{

   int y=f[x],z=f[y],k=(ch[y][1]==x);

    if(!be_root(y))ch[z][ch[z][1]==y]=x;

    f[x]=z;

    ch[y][k]=ch[x][!k],f[ch[x][!k]]=y;

    ch[x][!k]=y,f[y]=x;

    update(y),update(x);

}

void splay(int x)

{

    repush(x);

    while(!be_root(x)&&x)

    {

        int y=f[x],z=f[y];

        if(!be_root(y)&&y)

        {

            if((ch[y][1]==x)^(ch[z][1]==y))rotate(x);

            else rotate(y);

        }

        rotate(x);

    }

    update(x);

}

void access(int x)

{

    int y=0;

    while(x)

    {

        splay(x);

        ch[x][1]=y;

        update(x);

        y=x,x=f[x];

    }

}

void makeroot(int x)

{

    access(x),splay(x);

    swap(ch[x][0],ch[x][1]),fl[x]^=1;

}

void link(int x,int y)

{

    makeroot(x);

    f[x]=y;

}

void split(int x,int y)

{

    makeroot(x),access(y),splay(y);

}

void cut(int x,int y)

{

    split(x,y),ch[y][0]=f[x]=0,update(y);

}

int findf(int x)

{

    access(x),splay(x),pushdown(x);

    while(ch[x][0])x=ch[x][0],pushdown(x);

    return x;

}

inline int read()

{

    int f=1,x=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int main()

{

    n=read(),m=read(),Q=read();

    for(int i=1;i<=m;i++)

    {

        edge[i].l=read(),edge[i].r=read(),edge[i].v=read();

        if(edge[i].l>edge[i].r)swap(edge[i].l,edge[i].r);

    }

    sort(edge+1,edge+m+1);

    for(int i=1;i<=m;i++)M[make_pair(edge[i].l,edge[i].r)]=i;

    for(int i=1;i<=Q;i++)

    {

        q[i].typ=read(),q[i].x=read(),q[i].y=read();

        if(q[i].x>q[i].y)swap(q[i].x,q[i].y);

        if(q[i].typ==2)

        {

            int t=M[make_pair(q[i].x,q[i].y)];

            q[i].num=t,vis[t]=1;

        }

    }

    for(int i=1;i<=m;i++)maxx[i+n]=val[i+n]=i;

    for(int i=1;i<=m;i++)

    {

        if(vis[i])continue;

        int f1=findf(edge[i].l),f2=findf(edge[i].r);

        if(f1==f2)continue;

        link(edge[i].l,i+n),link(edge[i].r,i+n);

    }

    int temp=Q;

    while(Q)

    {

        if(q[Q].typ==1)

        {

            split(q[Q].x,q[Q].y);

            ret[Q]=edge[maxx[q[Q].y]].v;

        }else

        {

            split(q[Q].x,q[Q].y);

            int t=maxx[q[Q].y];

            if(edge[q[Q].num].v<edge[maxx[q[Q].y]].v)

            {

                cut(edge[t].l,t+n);

                cut(edge[t].r,t+n);

                link(edge[q[Q].num].l,q[Q].num+n);

                link(edge[q[Q].num].r,q[Q].num+n);

            }

        }

        Q--;

    }

    for(int i=1;i<=temp;i++)if(q[i].typ==1)printf("%d\n",ret[i]);

    return 0;

}

巴特西

bzoj 2594

最新文章

热门文章