引理

背景: 无向带权边图 G=(V,E)

  • case1:

    f(1, n)= \max_{e\in E’} \big(val_e\big) \vert_{min}

    E’\in E \text{ s.t. } 1\to n \text{连通}

    其实就是求G的最小生成树

答案就是1\to n树上路径的最大边权值

拓展到\forall u, v(u, v\in V), f(u, v)的求解同样成立.

  • case2:

    f(1, n) = \min_{e\in E’} \big(val_e\big) \vert_{max}

    E’\in E \text{ s.t.}1\to n \text{连通}

    将最小生成树换成最大生成树, 其他做法一致.

Proof

case 1 与 case 2 地位相同.

考虑反证, 讨论1 \to n 最小生成树路径上的答案与f(1,n)的关系.

sol

wrong sol: 将 (a + b) 作为键值排序, 从小到大加入边判连通

reason: 元素并不独立, 若当前枚举小于mid元素但答案可能会大于mid

Ac做法:

  • a从小到大排序
  • 依次加入边, Lct维护与b有关的最小生成树.

Code

%:pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 50;
const int inf = 1e9;

namespace {
    inline void read(int &x) {
        x = 0; char c = getchar();
        for(; !isdigit(c); c = getchar());
        for(;  isdigit(c); c = getchar())
            x = (x << 3) + (x << 1) + (c ^ '0');
    }
}


int n, m, ans = inf;
struct edge {
    int u, v, a, b;
    edge() {}
    edge(int u, int v, int a, int b) : 
        u(u), v(v), a(a), b(b) {}
    bool operator <(edge const &x) const {
        return a < x.a;
    }
} r[N * 2];

namespace Lct {
# define fa(x) t[x].fa
# define ls(x) t[x].ch[0]
# define rs(x) t[x].ch[1]
    struct node {
        int id, Mid;
        int fa, ch[2], tag;
        node() {} 
        node(int id) : id(id) {
            Mid = id;
            ch[0] = ch[1] = fa = tag = 0;
        }
    } t[N * 3];

    inline int ch(int x) { return rs(fa(x)) == x; }
    inline int isroot(int x) { return rs(fa(x)) != x && ls(fa(x)) != x; } 
    inline void connect(int u, int f, int c) { t[fa(u) = f].ch[c] = u; }
    inline int V(int x) {
        return x > n ? r[x - n].b : -inf;
    }
    inline void Max(int &x, int y) {
        if(V(y) > V(x)) x = y; 
    }
    inline void update(int u) {
        t[u].Mid = t[u].id;
        if(ls(u)) Max(t[u].Mid, t[ls(u)].Mid);
        if(rs(u)) Max(t[u].Mid, t[rs(u)].Mid);
    }
    inline void pushdown(int x) {
        if(!t[x].tag) return;
        swap(ls(x), rs(x));
        t[ls(x)].tag ^= 1, t[rs(x)].tag ^= 1;
        t[x].tag = 0;
    }
    void pushtag(int x) { 
        if(!isroot(x)) pushtag(fa(x)); 
        pushdown(x); 
    }
    void rotate(int x) {
        int y = fa(x), z = fa(y), d = ch(x);
        if(!isroot(y)) connect(x, z, ch(y)); 
        fa(x) = z;
        connect(t[x].ch[!d], y, d);
        connect(y, x, !d);
        update(y), update(x);
    }
    void splay(int x) {
        pushtag(x);
        while(!isroot(x)) {
            int y = fa(x);
            if(!isroot(y)) 
                (ch(x) ^ ch(y)) ? rotate(x) : rotate(y);
            rotate(x); 
        } 
    }
    void access(int x) {
        for(int y = 0; x; y = x, x = fa(x)) 
            splay(x), rs(x) = y, update(x);
    }
    int findrt(int x) {
        access(x), splay(x);
        for(; ls(x); x = ls(x), pushdown(x));
        return splay(x), x;
    }
    void mkrt(int x) { 
        access(x), splay(x), t[x].tag ^= 1; 
    }
    void link(int x, int y) { 
        mkrt(x), fa(x) = y; 
    }
    void cut(int x, int y) {
        mkrt(x), access(y), splay(y);
        if(ls(y) != x || rs(x)) return ;
        ls(y) = fa(x) = 0;
        update(y);
    }
    int query(int u, int v) {
        mkrt(u), access(v), splay(v);
        return t[v].Mid;
    }
# undef ls
# undef rs
}
using namespace Lct;

int main() {
    read(n), read(m);
    for(int i = 1; i <= m; ++i) 
        read(r[i].u), read(r[i].v), read(r[i].a), read(r[i].b);
    sort(r + 1, r + 1 + m);
    for(int i = 1; i <= n + m; ++i)
        t[i] = node(i);
    for(int i = 1; i <= m; ++i) {
        static int u, v;
        u = r[i].u, v = r[i].v;
        if(u == v) continue;

        if(findrt(u) != findrt(v)) {
            link(n + i, u);
            link(n + i, v);
        } else {
            int Maxp = query(u, v);
            if(V(Maxp) <= r[i].b) continue;
            cut(Maxp, r[Maxp - n].u);
            cut(Maxp, r[Maxp - n].v);
            link(n + i, u);
            link(n + i, v);
        }

        if(findrt(1) == findrt(n)) 
            ans = min(ans, r[i].a + V(query(1, n)));   
    }
    printf("%d\n", (ans == inf) ? -1 : ans);
    return 0;
}