[NOI2014][JZOJ3754][BZOJ3669]魔法森林

題目大意

給定一個 n 個點m條邊的無向圖。每條邊有兩個權值 (ai,bi) 。

你需要找到一條從 1 到n的路徑，使得路徑上 ai 最大值與 bi 最大值的和盡量小。

2≤n≤5×104,0≤m≤105,1≤ai,bi≤5×104

題目分析

這題看上去就很mst套路，實際上也是mst套路。

考慮從小到大枚舉路徑上 ai 的最大值，然後加入滿足條件的邊。

如果形成了環就删掉環上 bi 最大的邊。如果 1 和n是聯通的就更新答案。

使用LCT維護森林，使用并查集維護連通性。

時間複雜度 O(nlogn+nα(n)) 。

代碼實作

人生第一發lct居然很快就調過了，exciting!

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cctype>
#include <stack>

using namespace std;

int read()
{
    int x=,f=;
    char ch=getchar();
    while (!isdigit(ch)) f=ch=='-'?-:f,ch=getchar();
    while (isdigit(ch)) x=x*+ch-'0',ch=getchar();
    return x*f;
}

const int INF=;
const int N=;
const int M=;
const int V=N+M;

struct edge
{
    int x,y,a,b;

    bool operator<(edge const ed)const{return a<ed.a;}

    void load(){x=read(),y=read(),a=read(),b=read();}
}edg[M];

int fa[N],rank[N];
int n,m,ans;

struct link_cut_tree
{
    int par[V],fa[V],size[V],id[V],mx[V];
    int son[V][];
    stack<int> st;
    bool mark[V];

    bool side(int x){return son[fa[x]][]==x;}

    void R(int x){swap(son[x][],son[x][]),mark[x]^=;}

    void clear(int x)
    {
        if (mark[x])
        {
            if (son[x][]) R(son[x][]);
            if (son[x][]) R(son[x][]);
            mark[x]=;
        }
    }

    void update(int x)
    {
        size[x]=size[son[x][]]+size[son[x][]]+;
        mx[x]=edg[mx[son[x][]]].b>edg[mx[son[x][]]].b?mx[son[x][]]:mx[son[x][]];
        mx[x]=edg[id[x]].b>edg[mx[x]].b?id[x]:mx[x];
    }

    void pushdown(int x,int y)
    {
        for (;x!=y;st.push(x),x=fa[x]);
        for (;!st.empty();clear(st.top()),st.pop());
    }

    void rotate(int x)
    {
        int y=fa[x];bool s=side(x);
        if (fa[y]) son[fa[y]][side(y)]=x;
        if (son[x][s^]) fa[son[x][s^]]=y;
        son[y][s]=son[x][s^],son[x][s^]=y;
        fa[x]=fa[y],fa[y]=x;
        if (par[y]) par[x]=par[y],par[y]=;
        update(y),update(x);
    }

    void splay(int x,int y)
    {
        for (pushdown(x,y);fa[x]!=y;rotate(x))
            if (fa[fa[x]]!=y)
                if (side(x)==side(fa[x])) rotate(fa[x]);
                else rotate(x);
    }

    int access(int x)
    {
        int nxt=;
        for (;x;update(nxt=x),x=par[x])
        {
            splay(x,);
            if (son[x][]) fa[son[x][]]=,par[son[x][]]=x;
            son[x][]=nxt;
            if (nxt) fa[nxt]=x,par[nxt]=;
        }
        return nxt;
    }

    void makeroot(int x){R(access(x));}

    void link(int x,int y)
    {
        makeroot(x),access(x),splay(x,);
        par[x]=y,access(x);
    }

    void cut(int x,int y)
    {
        makeroot(x),access(y),splay(y,);
        fa[x]=son[y][]=,par[y]=,update(y);
    }

    int query(int x,int y)
    {
        makeroot(x),access(y),splay(y,);
        return mx[y];
    }
}lct;

int getfather(int son){return fa[son]==son?son:fa[son]=getfather(fa[son]);}

void merge(int x,int y)
{
    if (rank[x]>rank[y]) swap(x,y);
    fa[y]=x,rank[y]+=rank[x]==rank[y];
}

void calc()
{
    for (int i=;i<=n;++i) fa[i]=i;
    sort(edg+,edg++m),ans=INF;
    for (int i=;i<=n+m;++i) lct.size[i]=;
    for (int i=;i<=m;++i)
    {
        int x=edg[i].x,y=edg[i].y,fx=getfather(x),fy=getfather(y);
        if (fx!=fy) merge(fx,fy),lct.mx[i+n]=lct.id[i+n]=i,lct.link(x,i+n),lct.link(i+n,y);
        else
        {
            int id=lct.query(x,y);
            if (edg[id].b>edg[i].b)
            {
                int u=edg[id].x,v=edg[id].y;
                lct.cut(u,id+n),lct.cut(id+n,v);
                lct.mx[i+n]=lct.id[i+n]=i,lct.link(x,i+n),lct.link(i+n,y);
            }
        }
        if (getfather()==getfather(n)) ans=min(ans,edg[i].a+edg[lct.query(,n)].b);
    }
}

int main()
{
    freopen("forest.in","r",stdin),freopen("forest.out","w",stdout);
    n=read(),m=read();
    for (int i=;i<=m;++i) edg[i].load();
    calc();
    if (ans==INF) printf("-1\n");
    else printf("%d\n",ans);
    fclose(stdin),fclose(stdout);
    return ;
}