洛谷2387 [NOI2014]魔法森林

Luogu

BZOJ

分析

$\mathrm{LCT}$ 维护边权。

把所有的边按 $a$ 排序依次加入,同时维护 $b$ 的最小生成树即可。

如果不会维护边权,戳这里

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400010+10;

struct Edge { int u,v,a,b; } e[N];
bool operator <(Edge a,Edge b) { return a.a<b.a; }
int vis[N];

struct Link_Cut_Tree {
    int fa[N],ch[N][2],v[N],mx[N],rev[N];
    int sta[N];
    
    inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
    inline void reverse(int x) { swap(ch[x][0],ch[x][1]); rev[x]^=1; }
    inline int get(int x,int y) { return v[x]>v[y]?x:y; }
    
    inline void pushup(int x) {
        mx[x]=get(x,get(mx[ch[x][0]],mx[ch[x][1]]));
    }
    inline void pushdown(int x) {
        if (rev[x]) {
            if (ch[x][0]) reverse(ch[x][0]);
            if (ch[x][1]) reverse(ch[x][1]);
            rev[x]=0;
        }
    }
    
    inline void rotate(int x) {
        int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k];
        if (nroot(y)) ch[z][ch[z][1]==y]=x;
        ch[x][!k]=y,ch[y][k]=w;
        if (w) fa[w]=y; fa[y]=x,fa[x]=z;
        pushup(y);
    }
    inline void splay(int x) {
        int y=x,z=0; sta[++z]=y;
        while (nroot(y)) sta[++z]=y=fa[y];
        while (z) pushdown(sta[z--]);
        while (nroot(x)) {
            y=fa[x],z=fa[y];
            if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
            rotate(x);
        }
        pushup(x);
    }
    
    inline void access(int x) {
        for (re int y=0;x;x=fa[y=x])
            splay(x),ch[x][1]=y,pushup(x);
    }
    inline void makeroot(int x) { access(x),splay(x),reverse(x); }
    inline int findroot(int x) {
        access(x); splay(x);
        while (ch[x][0]) pushdown(x),x=ch[x][0];
        return x;
    }
    inline void split(int x,int y) { makeroot(x),access(y),splay(y); }
    inline void link(int x,int y) { makeroot(x),fa[x]=y; }
    inline void cut(int x,int y) { split(x,y),fa[x]=ch[y][0]=0,pushup(y); }
} T;

int main() {
    int n=read(),m=read();
    for (re int i=1;i<=m;++i) e[i]=(Edge){read(),read(),read(),read()};
    sort(e+1,e+m+1); int ans=2e9;
    for (re int i=1;i<=m;++i) {
        T.v[i+n]=e[i].b; int u=e[i].u,v=e[i].v;
        if (u==v) continue;
        if (T.findroot(u)!=T.findroot(v)) T.link(u,i+n),T.link(v,i+n);
        else {
            T.split(u,v); int t=T.mx[v]-n;
            if (e[i].b<e[t].b) {
                T.cut(e[t].u,t+n),T.cut(e[t].v,t+n);
                T.link(u,i+n),T.link(v,i+n);
            }
        }
        if (T.findroot(1)==T.findroot(n)) {
            T.split(1,n);
            ans=min(ans,e[i].a+e[T.mx[n]-n].b);
        }
    }
    if (ans==2e9) puts("-1");
    else printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 41 PM

发表评论