[BZOJ2959]长跑(LCT,并查集)

发布于 2018-01-22  120 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2959]长跑(LCT,并查集)

Description

某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”,同学们纷纷离开寝室,离开教室,离开实验室,到操场参加3000米长跑运动。一时间操场上熙熙攘攘,摩肩接踵,盛况空前。
  为了让同学们更好地监督自己,学校推行了刷卡机制。
  学校中有n个地点,用1到n的整数表示,每个地点设有若干个刷卡机。
  有以下三类事件:
  1、修建了一条连接A地点和B地点的跑道。
  2、A点的刷卡机台数变为了B。
  3、进行了一次长跑。问一个同学从A出发,最后到达B最多可以刷卡多少次。具体的要求如下:
  当同学到达一个地点时,他可以在这里的每一台刷卡机上都刷卡。但每台刷卡机只能刷卡一次,即使多次到达同一地点也不能多次刷卡。
  为了安全起见,每条跑道都需要设定一个方向,这条跑道只能按照这个方向单向通行。最多的刷卡次数即为在任意设定跑道方向,按照任意路径从A地点到B地点能刷卡的最多次数。

Http

BZOJ

Tag

LCT,并查集

解决思路

算是这题的强化板。
先看题目中关于单向方向的设置,讲得那么复杂,其实就是要求不能走一条边再反向返回,那么说白了就是从\(u\)到\(v\)的话可以走环和直接路径,不能走到一棵子树中去再原路返回。
看到环一定是可以走的,所以我们可以把环缩成一个点,那么就直接动态求两点之间的路径点权和即可。
综上,并查集维护缩点,\(LCT\)维护动态路径点权和。
需要注意的是,第二个操作是修改某一个点上的机器数量,而我们缩点后并没有统计单个点的贡献,所以要在另外存一下原来每一个点的机器数,方便修改。
最后就是与这题一样需要注意,因为我们缩了点,所以在\(LCT\)中每一步都要\(find\)一下缩点后的编号

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=150010;
const int inf=2147483647;

class Splay_Data
{
public:
    int fa,ch[2];
    int key,size;//key代表的是这个点上的机器数(包括缩点后id是它的点),size则是子树的
    int rev;
};

int n;
Splay_Data S[maxN];
int UFS[maxN],Id[maxN];//UFS是标记是否在同一联通块,ID是标记缩点后的编号,这两个都是并查集
int Stack[maxN];
int Mach[maxN];//存放每一个点机器数,注意这里不是缩点后的编号

int Find(int *f,int x);
bool Isroot(int x);
void PushDown(int x);
void Update(int x);
void Rotate(int x);
void Splay(int x);
void Access(int x);
int Findroot(int x);
void Makeroot(int x);
void Link(int x,int y);
void Cut(int x,int y);
void Add_Edge(int u,int v);
void dfs(int now,int fa);

int main()
{
    int Q;
    scanf("%d%d",&n,&Q);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&Mach[i]);
        S[i].key=S[i].size=Mach[i],UFS[i]=i,Id[i]=i;
    }
    while (Q--)
    {
        int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
        if (opt==1) Add_Edge(Find(Id,x),Find(Id,y));
        if (opt==2)
        {
            int xx=Find(Id,x);//注意这里,要先减去原来的机器数再加上现在的机器数
            Makeroot(xx);S[xx].key+=y-Mach[x];Update(xx);Mach[x]=y;
        }
        if (opt==3)
        {
            x=Find(Id,x);y=Find(Id,y);
            if (Find(UFS,x)!=Find(UFS,y)) printf("-1\n");
            else
            {
                Makeroot(x);Access(y);Splay(y);
                printf("%d\n",S[y].size);
            }
        }
    }
    return 0;
}

int Find(int *f,int x)
{
    if (f[x]!=x) f[x]=Find(f,f[x]);
    return f[x];
}

bool Isroot(int x)
{
    int fa=Find(Id,S[x].fa);
    if ((S[fa].ch[0]==x)||(S[fa].ch[1]==x)) return 0;
    return 1;
}

void PushDown(int x)
{
    if (S[x].rev)
    {
        S[x].rev=0;
        int lson=S[x].ch[0],rson=S[x].ch[1];
        swap(S[lson].ch[0],S[lson].ch[1]);
        swap(S[rson].ch[0],S[rson].ch[1]);
        if (lson) S[lson].rev^=1;
        if (rson) S[rson].rev^=1;
    }
    return;
}

void Update(int x)
{
    S[x].size=S[S[x].ch[0]].size+S[S[x].ch[1]].size+S[x].key;
    return;
}

void Rotate(int x)
{
    int y=Find(Id,S[x].fa),z=Find(Id,S[y].fa);
    int sx=(x==S[y].ch[1]);
    int sy=(y==S[z].ch[1]);
    S[x].fa=z;if (Isroot(y)==0) S[z].ch[sy]=x;
    S[y].ch[sx]=S[x].ch[sx^1];if (S[x].ch[sx^1]) S[S[x].ch[sx^1]].fa=y;
    S[y].fa=x;S[x].ch[sx^1]=y;
    Update(y);
    return;
}

void Splay(int x)
{
    int now=x;int stacktop=1;Stack[1]=x;
    while (Isroot(now)==0)
    {
        Stack[++stacktop]=Find(Id,S[now].fa);
        now=Find(Id,S[now].fa);
    }
    for (int i=stacktop;i>=1;i--) PushDown(Stack[i]);
    while (Isroot(x)==0)
    {
        int y=Find(Id,S[x].fa);int z=Find(Id,S[y].fa);
        if (Isroot(y)==0)
            ((x==S[y].ch[0])^(y==S[z].ch[0]))?(Rotate(x)):(Rotate(y));
        Rotate(x);
    }
    Update(x);
    return;
}

void Access(int x)
{
    int lastx=0;
    while(x)
    {
        Splay(x);S[x].ch[1]=lastx;
        Update(x);lastx=x;x=Find(Id,S[x].fa);
    }
    return;
}

int Findroot(int x)
{
    Access(x);Splay(x);
    int now=x;
    while (S[now].ch[0]) now=S[now].ch[0];
    return now;
}

void Makeroot(int x)
{
    Access(x);Splay(x);
    S[x].rev^=1;swap(S[x].ch[0],S[x].ch[1]);
    return;
}

void Link(int x,int y)
{
    Makeroot(x);S[x].fa=y;
    return;
}

void Cut(int x,int y)
{
    Makeroot(x);Access(y);Splay(y);
    S[x].fa=S[y].ch[0]=0;Update(y);
    return;
}

void Add_Edge(int u,int v)
{
    if (Find(UFS,u)!=Find(UFS,v))
    {
        UFS[Find(UFS,u)]=Find(UFS,v);
        Link(u,v);
        return;
    }
    else
    {
        Makeroot(u);Access(v);Splay(v);
        dfs(v,v);//把整棵v的所在的splay都缩到v上,把信息都压缩到v中
        S[v].ch[0]=S[v].ch[1]=0;
    }
    return;
}

void dfs(int now,int fa)
{
    if (now!=fa) S[fa].key+=S[now].key,Id[now]=fa;
    if (S[now].ch[0]) dfs(S[now].ch[0],fa);
    if (S[now].ch[1]) dfs(S[now].ch[1],fa);
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2959]长跑(LCT,并查集)


HNCJ OIer