洛谷2387 BZOJ3669魔法森林题解

题目链接

BZ链接

这道题被很多人用spfa水了过去，表示很。。。

其实spfa很好卡，这组数据可以卡掉大多数spfa

链接：密码：rjvk

这里讲一下LCT的做法

我们按照a将边排序，然后依次添加

每次加入时若两边没有联通，就直接加入，否则就

检查两边的路径中权值b最大的权值是多少，如果大于当前加入边的权值

就将该边删掉，然后将当前边加入

注意lct维护边权时需要用到拆点

# include<iostream>

# include<algorithm>

# include<cmath>

# include<cstring>

# include<cstdio>

using namespace std;

const int mn = ;

const int inf = ;

struct edge{int u,v,a,b;};

edge e[mn];

bool cmp(const edge &x,const edge &y)

{

    if(x.a==y.a) return x.b<y.b;

    else return x.a<y.a;

}

int n,m,ans,fa[mn];

int _find(int x) {return x==fa[x] ? x : fa[x]=_find(fa[x]);}

struct LCT{

    int val[mn],fa[mn],c[mn][],mx[mn],st[mn];

    //mx[x]表示子树中权值最大的点的编号

    bool rev[mn];

    bool nroot(int x)

    {

        return c[fa[x]][]==x || c[fa[x]][]==x;

    }

    void zhuan(int x)

    {

        swap(c[x][],c[x][]);

        rev[x]^=;

    }

    void pushdown(int x)

    {

        if(rev[x])

        {

            rev[x]=;

            if(c[x][]) zhuan(c[x][]);

            if(c[x][]) zhuan(c[x][]);

        }

    }

    void updown(int x)

    {

        mx[x]=x;

        if(c[x][])

        {

            if(val[mx[c[x][]]]>val[mx[x]])

               mx[x]=mx[c[x][]];

        }

        if(c[x][])

        {

            if(val[mx[c[x][]]]>val[mx[x]])

               mx[x]=mx[c[x][]];

        }

    }

    void rotate(int x)

    {

        int y=fa[x],z=fa[y],flag;

        if(c[y][]==x) flag=;

        else flag=;

        if(nroot(y))

        {

            if(c[z][]==y) c[z][]=x;

            else c[z][]=x;

        }

        c[y][flag^]=c[x][flag],fa[c[x][flag]]=y;

        c[x][flag]=y;

        fa[y]=x,fa[x]=z;

        updown(y);

        updown(x);

    }

    void splay(int x)

    {

        int top=;

        st[++top]=x;

        for(int i=x;nroot(i);i=fa[i])

           st[++top]=fa[i];

        for(;top;top--) pushdown(st[top]);

        while(nroot(x))

        {

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

            if(nroot(y))

            {

                if((c[y][]==x) ^ (c[z][]==y))

                  rotate(x);

                else rotate(y);

            }

            rotate(x);

        }

        updown(x);

    }

    void access(int x)

    {

       int t=;

       while(x){splay(x);c[x][]=t;updown(x);t=x;x=fa[x];}

    }

    void makeroot(int x)

    {

        access(x);

        splay(x);

        zhuan(x);

    }

    void link(int x,int y)

    {

        makeroot(x);

        fa[x]=y;

    }

    void cut(int x,int y)

    {

        makeroot(x);

        access(y);

        splay(y);

        c[y][]=fa[x]=;

        updown(y);

    }

    int query(int x,int y)

    {

        makeroot(x);

        access(y);

        splay(y);

        return mx[y];

    }

}T;

void pre()

{

    for(int i=;i<=n;i++)

      fa[i]=i;

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

      T.val[i+n]=e[i].b;

}

int main()

{

    scanf("%d%d",&n,&m);

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

       scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].a,&e[i].b);

    sort(e+,e++m,cmp);

    ans=inf;

    pre();

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

    printf("%d %d\n",e[i].a,e[i].b);*/

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

    {

        int x=e[i].u,y=e[i].v;

        int xx=_find(x),yy=_find(y);

        if(xx!=yy)

        {

            fa[xx]=yy;

            T.link(x,i+n);

            T.link(i+n,y);

        }

        else {

            int k=T.query(x,y);

            if(T.val[k]>e[i].b)

            {

                T.cut(e[k-n].u,k);

                T.cut(k,e[k-n].v);

                T.link(x,i+n);

                T.link(i+n,y);

            }

        }

        if(_find()==_find(n))

          ans=min(ans,e[i].a+T.val[T.query(,n)]);

    //  printf("%d %d\n",e[i].a,T.query(1,n));

    }

    if(ans==inf) printf("-1");

    else printf("%d",ans);

    return ;

}

洛谷2387 BZOJ3669魔法森林题解的相关教程结束。