「luogu2387」[NOI2014] 魔法森林

题目大意

\(n\) 个点 \(m\) 条边的无向图，每条边上有两个权值 \(a,b\)，求从 \(1\) 节点到 \(n\) 节点 \(max\{a\}+max\{b\}\) 的最小值。图中可能有重边和自环。\((n \leq 5 \times 10^4 , m \leq 10^5)\)

一句话题解

考虑生成树 ( 过程类似 \(kruskal​\) )；

把边按照 \(a\) 从小到大排序，\(1-m\) 枚举边，设边连接的两点为 \(u , v\)；

若 \(u , v\) 已经在一个联通块中，则在 \(u\) 到 \(v\) 的路径中找一个 \(b\) 的最大值 \(b_{max}\)，如果 \(b_{max} > b当前枚举到的边\)，就把 \(当前枚举到的边\) 连接，\(max_b\) 所在的边断开；

若 \(u , v\) 不在一个联通块中，则直接连接；

边用 \(lct\) 维护即可；

代码如下：

#include <cstdio>

#include <cstring>

#include <algorithm>

inline int in() {

    int x=0;char c=getchar();bool f=false;

    while(c<'0'||c>'9') f|=c=='-', c=getchar();

    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48), c=getchar();

    return f?-x:x;

}

const int N = 5e4+5, M = 1e5+5;

struct edge {

    int u, v, a, b;

    friend inline bool operator < (const edge &x, const edge &y) {

        return x.a < y.a;

    }

}e[M];

int n, m;

template<typename T>inline void chk_min(T &_, T __) { _=_<__?_:__; }

struct link_cut_tree {

#define lson c[p][0]

#define rson c[p][1]

    int c[N+M][2], fa[N+M], val[N+M], max[N+M];

    bool rev[N+M];

    inline bool nroot(int p) {

        return c[fa[p]][0]==p||c[fa[p]][1]==p;

    }

    inline void push_up(int p) {

        max[p]=p;

        if(lson&&val[max[lson]]>val[max[p]]) max[p]=max[lson];

        if(rson&&val[max[rson]]>val[max[p]]) max[p]=max[rson];

    }

    inline void rever(int p) {

        std::swap(lson, rson);

        rev[p]^=1;

    }

    inline void push_down(int p) {

        if(rev[p]) {

            if(lson) rever(lson);

            if(rson) rever(rson);

            rev[p]=false;

        }

    }

    void push_all(int p) {

        if(nroot(p)) push_all(fa[p]);

        push_down(p);

    }

    inline void rotate(int x) {

        int y=fa[x], z=fa[y], l=c[y][1]==x, r=l^1;

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

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

        c[y][l]=c[x][r], c[x][r]=y;

        push_up(y), push_up(x);

    }

    inline void splay(int x) {

        int y, z;

        push_all(x);

        while(nroot(x)) {

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

            if(nroot(y)) rotate(c[y][0]==x^c[z][0]==y?x:y);

            rotate(x);

        }

    }

    inline void access(int p) { for(int s=0;p;p=fa[s=p]) splay(p), rson=s, push_up(p); }

    inline void make_root(int p) { access(p), splay(p), rever(p); }

    inline void split(int p, int s) { make_root(p), access(s), splay(s); }

    inline void link(int p, int s) { make_root(p), fa[p]=s; }

    inline void cut(int p, int s) { split(p, s), c[s][0]=fa[p]=0, push_up(s); }

    inline int select(int p, int s) { split(p, s); return max[s]; }

#undef lson

#undef rson

}lct;

struct disjoint_set_union {

    int fa[N];

    int get_fa(int u) { return u==fa[u]?u:fa[u]=get_fa(fa[u]); }

    inline int & operator [] (int u) { return fa[u]; }

}dsu;

inline int kruskal() {

    int ret=-1;

    std::sort(e+1, e+1+m);

    for(int i=1;i<=n;++i) dsu[i]=i;

    for(int i=n+1;i<=n+m;++i) lct.val[i]=e[i-n].b;

    for(int i=1;i<=n+m;++i) lct.max[i]=i;

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

        if(e[i].u==e[i].v) continue;

        int u=dsu.get_fa(e[i].u), v=dsu.get_fa(e[i].v);

        if(u==v) {

            int k=lct.select(e[i].u, e[i].v);

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

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

                lct.link(e[i].u, i+n), lct.link(i+n, e[i].v);

            }

        }

        else {

            dsu[u]=v;

            lct.link(e[i].u, i+n), lct.link(i+n, e[i].v);

        }

        if(dsu.get_fa(1)==dsu.get_fa(n)) {

            lct.split(1, n);

            if(ret==-1) ret=lct.val[lct.max[n]]+e[i].a;

            else        chk_min(ret, lct.val[lct.max[n]]+e[i].a);

        }

    }

    return ret;

}

int main() {

    n=in(), m=in();

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

        e[i]=(edge){in(), in(), in(), in()};

    printf("%d\n", kruskal());

    return 0;

}