[BZOJ3669/Luogu2387][Noi2014]魔法森林(LCT)

发布于 2018-01-24  115 次阅读


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

本文链接地址:[BZOJ3669/Luogu2387][Noi2014]魔法森林(LCT)

Description

为了得到书法大家的真传,小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图,节点标号为1..N,边标号为1..M。初始时小E同学在号节点1,隐士则住在号节点N。小E需要通过这一片魔法森林,才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候,这条边上的妖怪就会对其发起攻击。幸运的是,在号节点住着两种守护精灵:A型守护精灵与B型守护精灵。小E可以借助它们的力量,达到自己的目的。
只要小E带上足够多的守护精灵,妖怪们就不会发起攻击了。具体来说,无向图中的每一条边Ei包含两个权值Ai与Bi。若身上携带的A型守护精灵个数不少于Ai,且B型守护精灵个数不少于Bi,这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小E发起攻击,他才能成功找到隐士。
由于携带守护精灵是一件非常麻烦的事,小E想要知道,要能够成功拜访到隐士,最少需要携带守护精灵的总个数。守护精灵的总个数为A型守护精灵的个数与B型守护精灵的个数之和。

Http

BZOJ
Luogu

Tag

LCT

题目大意

求一条\(1\)到\(n\)的路径使得路径中最大的\(a\)和\(b\)之和最小

解决思路

把边权按照\(a\)排序,从小到大依此插入,动态维护最小生成树。
关于\(LCT\)维护最小生成树,可以参考这里

代码

#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=50010+100010;
const int maxM=100010;
const int inf=2147483647;

class Splay_Data
{
public:
    int fa,ch[2];
    int rev;
    int key,mxid;
    int d1,d2;
};

class Edge
{
public:
    int u,v,a,b;
};

bool operator < (Edge A,Edge B)
{
    return A.a<B.a;
}

int n,m;
int nodecnt;
Splay_Data S[maxN];
int Stack[maxN];
int UFS[maxN];
Edge E[maxM];

bool Isroot(int x);
void Update(int x);
void PushDown(int x);
void Rotate(int x);
void Splay(int x);
void Access(int x);
void Makeroot(int x);
int Findroot(int x);
void Link(int x,int y);
void Cut(int x,int y);
int GetMax(int a,int b);
int Find(int x);
void Add_Edge(int u,int v,int w);
bool Delete(int u,int v,int w);

int main()
{
    scanf("%d%d",&n,&m);
    nodecnt=n+1;
    for (int i=1;i<=n;i++) S[i].key=0,UFS[i]=i;
    for (int i=1;i<=m;i++) scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].a,&E[i].b);
    sort(&E[1],&E[m+1]);//排序边
    int Ans=inf;
    for (int i=1;i<=m;i++)//依此插入边权
    {
        if (E[i].u==E[i].v) continue;
        Add_Edge(E[i].u,E[i].v,E[i].b);
        if (Find(1)==Find(n))
        {
            Makeroot(1);Access(n);Splay(n);
            Ans=min(Ans,E[i].a+S[S[n].mxid].key);
        }
    }
    if (Ans!=inf) printf("%d\n",Ans);
    else printf("-1\n");
    return 0;
}

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

void Update(int x)
{
    S[x].mxid=GetMax(x,GetMax(S[S[x].ch[0]].mxid,S[S[x].ch[1]].mxid));
    return;
}

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 Rotate(int x)
{
    int y=S[x].fa,z=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[x].ch[sx^1]=y;S[y].fa=x;
    Update(y);
    return;
}

void Splay(int x)
{
    int now=x,stacktop=1;Stack[1]=x;
    while (Isroot(now)==0)
    {
        Stack[++stacktop]=S[now].fa;
        now=S[now].fa;
    }
    for (int i=stacktop;i>=1;i--) PushDown(Stack[i]);
    while (Isroot(x)==0)
    {
        int y=S[x].fa,z=S[y].fa;
        if (Isroot(y)==0)
            ((x==S[y].ch[1])^(y==S[z].ch[1]))?(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=S[x].fa;
    }
    return;
}

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

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

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

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

int GetMax(int a,int b)
{
    return (S[a].key<S[b].key)?(b):(a);
}

int Find(int x)
{
    if (UFS[x]!=x) UFS[x]=Find(UFS[x]);
    return UFS[x];
}

bool Delete(int u,int v,int w)
{
    Makeroot(u);Access(v);Splay(v);
    int eid=S[v].mxid;
    if (S[eid].key<=w) return 0;
    Cut(eid,S[eid].d1);Cut(eid,S[eid].d2);
    return 1;
}

void Add_Edge(int u,int v,int w)
{
    if (Find(u)==Find(v))
        if (Delete(u,v,w)==0) return;
    UFS[Find(u)]=Find(v);
    int eid=++nodecnt;
    Makeroot(u);Makeroot(v);
    S[u].fa=S[v].fa=eid;
    S[eid].d1=u;S[eid].d2=v;
    S[eid].key=w;
    return;
}

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

本文链接地址:[BZOJ3669/Luogu2387][Noi2014]魔法森林(LCT)


HNCJ OIer