【BZOJ3669】【NOI2014】魔法森林 LCT

题目描述

给你一个\(n\)个点\(m\)条边的图，每条边有两个边权\(a,b\)。请你找出从\(1\)到\(n\)一条路径，使得这条路径上边权\(a\)的最大值\(+\)边权\(b\)的最大值最小。

\(n\leq 50000,m\leq 100000\)

题解

我们可以考虑求出当边权\(a\leq\)某个数时边权\(b\)的最大值。

先把边按边权\(a\)从小到大排序，依次加入，用LCT维护当前边权\(b\)的最小生成树。如果这两个点已经联通，就判断这两个点路径上边的边权\(b\)的最大值，如果大于当前这条边的边权\(b\)，就把这条边删掉。否则就不加入这条边。

每加完一条边我们就可以认为从\(1\)到\(n\)的边权\(a\)的最大值为当前这条边的边权\(a\)（否则就会在之前更新到），然后查询\(1\)到\(n\)的边权\(b\)的最大值，更新答案。

时间复杂度：\(O(m\log n)\)

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
namespace lct
{
    int a[200010][2];
    int f[200010];
    pii v[200010];
    pii s[200010];
    int r[200010];
    int root(int x)
    {
        return !f[x]||(a[f[x]][0]!=x&&a[f[x]][1]!=x);
    }
    void reverse(int x)
    {
        swap(a[x][0],a[x][1]);
        r[x]^=1;
    }
    void push(int x)
    {
        if(r[x])
        {
            if(a[x][0])
                reverse(a[x][0]);
            if(a[x][1])
                reverse(a[x][1]);
            r[x]=0;
        }
    }
    void mt(int x)
    {
        s[x]=max(v[x],max(s[a[x][0]],s[a[x][1]]));
    }
    void rotate(int x)
    {
        if(root(x))
            return;
        int p=f[x];
        int q=f[p];
        int ps=(x==a[p][1]);
        int qs=(p==a[q][1]);
        int ch=a[x][ps^1];
        if(!root(p))
            a[q][qs]=x;
        a[x][ps^1]=p;
        a[p][ps]=ch;
        if(ch)
            f[ch]=p;
        f[p]=x;
        f[x]=q;
        mt(p);
        mt(x);
    }
    void clear(int x)
    {
        if(!root(x))
            clear(f[x]);
        push(x);
    }
    void splay(int x)
    {
        clear(x);
        int p,q;
        while(!root(x))
        {
            p=f[x];
            if(!root(p))
            {
                q=f[p];
                if((p==a[q][1])==(x==a[p][1]))
                    rotate(p);
                else
                    rotate(x);
            }
            rotate(x);
        }
    }
    void access(int x)
    {
        int y=x,t=0;
        while(x)
        {
            splay(x);
            a[x][1]=t;
            mt(x);
            t=x;
            x=f[x];
        }
        splay(y);
    }
    void change(int x)
    {
        access(x);
        reverse(x);
    }
    int findroot(int x)
    {
        access(x);
        while(a[x][0])
            x=a[x][0];
        splay(x);
        return x;
    }
    pii query(int x,int y)
    {
        change(x);
        access(y);
        return s[y];
    }
    void link(int x,int y)
    {
        change(x);
        f[x]=y;
    }
    void cut(int x,int y)
    {
        change(x);
        access(y);
        f[a[y][0]]=0;
        a[y][0]=0;
        mt(y);
    }
}
struct edge
{
    int x,y;
    int a,b;
};
edge a[100010];
int cmp(edge a,edge b)
{
    return a.a<b.a;
}
int main()
{
//  freopen("bzoj3669.in","r",stdin);
//  freopen("bzoj3669.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    for(i=1;i<=m;i++)
        scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].a,&a[i].b);
    sort(a+1,a+m+1,cmp);
    int ans=0x7fffffff;
    for(i=1;i<=m;i++)
    {
        if(a[i].x==a[i].y)
            continue;
        if(lct::findroot(a[i].x)==lct::findroot(a[i].y))
        {
            pii s=lct::query(a[i].x,a[i].y);
            if(a[i].b>=a[s.second].b)
                continue;
            lct::cut(s.second+n,a[s.second].x);
            lct::cut(s.second+n,a[s.second].y);
        }
        lct::v[i+n]=pii(a[i].b,i);
        lct::link(a[i].x,i+n);
        lct::link(a[i].y,i+n);
        if(lct::findroot(1)==lct::findroot(n))
            ans=min(ans,a[i].a+lct::query(1,n).first);
    }
    if(ans==0x7fffffff)
        ans=-1;
    printf("%d\n",ans);
    return 0;
}