Luogu2387 [NOI2014]魔法森林

Link

Solution

感觉自己做完全靠蒙和猜，尽管是正解但并不知道为什么。看了题解才知道原来是生成树满足这个性质。

暴力可以枚举\(max\{a\}\)，然后在此条件下找\(max\{b\}\)最小的\(1\)到\(n\)的路径。

优化可以参照kruskal的思想。

先把所有边按\(a_i\)从小到大排序。维护一个\(b\)的最小生成树。依次枚举每条边，那么此时\(a_i\)就是全局最大的\(a\)。如果加入这条边不形成环，就直接加入。如果形成环，根据生成树的回路性质，某个回路中的权值最大边恰好有一条不在最小生成树中（引用自luogu题解）。所以找到环上\(max\{b\}\)，和\(b_i\)做比较，如果\(b_i\)较小就用这条边替换。

答案就是\(1\)和\(n\)联通以后每次的\(a_i+max\{b_k\}(k\in Path_{1\rightarrow n})\)取\(min\)。\(Path_{1\rightarrow n}\)指\(1\)到\(n\)的路径。

考虑为什么这样是对的。如果这条边在\(1\)到\(n\)路径上，显然是对的。如果不在，那么\(1\)到\(n\)路径上的\(max\{a\}\)肯定不大于\(a_i\)，那么一定在以前枚举过这条边，更新过答案。所以这一次并不会对答案造成影响。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,a,b) for(int i=(a),ed=(b);i<=ed;++i)
inline int read(){
    register int x=0,f=1;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
    return f?x:-x;
}

const int N=5e4+10,M=1e5+10;
int n,m,ans=0x7fffffff,f[N];
struct edge{int x,y,a,b;inline bool operator<(const edge &s){return a<s.a;}}e[M];
inline int find(int x){return f[x]=(f[x]==x?f[x]:find(f[x]));}

namespace LinkCutTree{
    const int _=N+M;
    int fa[_],ch[_][2],r[_],mx[_],v[_];
    inline int Max(int x,int y){return v[x]<v[y]?y:x;}
    inline void pushup(int x){mx[x]=Max(x,Max(mx[ch[x][0]],mx[ch[x][1]]));}
    inline void pushr(int x){swap(ch[x][0],ch[x][1]);r[x]^=1;}
    inline void pushdown(int x){if(r[x])pushr(ch[x][0]),pushr(ch[x][1]),r[x]=0;}
    inline int getdir(int x){return x==ch[fa[x]][1];}
    inline bool noroot(int x){return x==ch[fa[x]][0]||x==ch[fa[x]][1];}
    inline void rotate(int x){
        int f=fa[x],p=fa[f],k=getdir(x),s=ch[x][k^1];
        ch[x][k^1]=f;ch[f][k]=s;if(noroot(f))ch[p][getdir(f)]=x;
        fa[f]=x;fa[x]=p;if(s)fa[s]=f;
        pushup(f);
    }
    inline void splay(int x){
        static int stk[_];
        int tp=0,y=x;stk[++tp]=y;
        while(noroot(y))stk[++tp]=y=fa[y];
        while(tp)pushdown(stk[tp--]);
        for(int f=fa[x];noroot(x);rotate(x),f=fa[x])
            if(noroot(f))rotate(getdir(f)==getdir(x)?f:x);
        pushup(x);
    }
    inline void access(int x){
        for(int y=0;x;y=x,x=fa[x])
            splay(x),ch[x][1]=y,pushup(x);
    }
    inline void makeroot(int x){
        access(x),splay(x),pushr(x);
    }
    inline void split(int x,int y){
        makeroot(x);access(y);splay(y);
    }
    inline void cut(int x,int y){
        split(x,y);
        fa[x]=ch[y][0]=0;
    }
}using namespace LinkCutTree;

int main(){
    n=read(),m=read();
    REP(i,1,m)e[i]=(edge){read(),read(),read(),read()};
    sort(e+1,e+m+1);
    REP(i,1,n)f[i]=i;
    REP(t,1,m){
        if(e[t].x==e[t].y)continue;
        int x=find(e[t].x),y=find(e[t].y);
        if(x^y){
            f[x]=y;x=e[t].x,y=e[t].y;
            v[n+t]=e[t].b;
            makeroot(x);fa[fa[x]=n+t]=y;
        }
        else{
            x=e[t].x,y=e[t].y;
            split(x,y);int s=mx[y];
            if(v[s]>e[t].b){
                cut(x,s);cut(y,s);
                v[n+t]=e[t].b;
                makeroot(x);fa[fa[x]=n+t]=y;
            }
        }
        if(find(1)==find(n)){
            split(1,n);
            ans=min(ans,e[t].a+e[mx[n]-n].b);
        }
    }
    if(ans<(int)0x7fffffff)printf("%d\n",ans);
    else puts("-1");
    return 0;
}

Luogu2387 [NOI2014]魔法森林

原文：https://www.cnblogs.com/fruitea/p/12128379.html