题目地址：洛谷：【P2387】[NOI2014]魔法森林 – 洛谷、BZOJ：Problem 3669. — [Noi2014]魔法森林

题目描述

为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐 士。魔法森林可以被看成一个包含 n 个节点 m 条边的无向图，节点标号为 1,2,3,…,n，边标号为 1,2,3,…,m。初始时小 E 同学在 1 号节点，隐士则住在 n 号节点。小 E 需要通过这一片魔法森林，才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪 就会对其发起攻击。幸运的是，在 1 号节点住着两种守护精灵：A 型守护精灵与 B 型守护精灵。小 E 可以借助它们的力量，达到自己的目的。
只要小 E 带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无 向图中的每一条边 ei 包含两个权值 ai 与 bi 。若身上携带的 A 型守护精灵个数不 少于 ai ，且 B 型守护精灵个数不少于 bi ，这条边上的妖怪就不会对通过这条边 的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向 小 E 发起攻击，他才能成功找到隐士。
由于携带守护精灵是一件非常麻烦的事，小 E 想要知道，要能够成功拜访到 隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的 个数与 B 型守护精灵的个数之和。

输入输出格式

输入格式：
输入文件的第 1 行包含两个整数 n,m，表示无向图共有 n 个节点，m 条边。 接下来 m 行，第i+ 1 行包含 4 个正整数 Xi,Yi,ai,bi，描述第i条无向边。 其中Xi与 Yi为该边两个端点的标号，ai 与 bi 的含义如题所述。 注意数据中可能包含重边与自环。

输出格式：
输出一行一个整数：如果小 E 可以成功拜访到隐士，输出小 E 最少需要携 带的守护精灵的总个数；如果无论如何小 E 都无法拜访到隐士，输出“-1”（不含引号）。

输入输出样例

输入样例#1：

4 5 
1 2 19 1 
2 3 8 12 
2 4 12 15 
1 3 17 8 
3 4 1 17 

输出样例#1：

32

输入样例#2：

3 1 
1 2 1 1 

输出样例#2：

-1

说明

2<=n<=50000, 0<=m<=100000

题解

本题可以使用LCT维护最小生成树动态加边的办法。一条边有两个边权，不好处理，我们将所有的边按照一个边权a排序，依次插入，并每次都用当前答案更新答案。遇到该边的两个点已是连通状态，如果这条路径上存在比当前边的边权b还大的边，就删去路径上的该边，否则不插入这条边。我们可以把边权放在点上，插入一条边变成使边的两端点向代表边的点连接。

代码

// Code by KSkun, 2018/4
#include <cstdio>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 150005, INF = 1e9;

struct Node {
    int val, mx, ch[2], fa;
    bool rev;
} tr[MAXN];

inline bool isleft(int p) {
    return tr[tr[p].fa].ch[0] == p;
}

inline bool isroot(int p) {
    int fa = tr[p].fa;
    return tr[fa].ch[0] != p && tr[fa].ch[1] != p;
} 

inline void update(int p) {
    int lch = tr[p].ch[0], rch = tr[p].ch[1];
    tr[p].mx = p;
    if(tr[tr[lch].mx].val > tr[tr[p].mx].val) tr[p].mx = tr[lch].mx;
    if(tr[tr[rch].mx].val > tr[tr[p].mx].val) tr[p].mx = tr[rch].mx;
}

inline void reverse(int p) {
    std::swap(tr[p].ch[0], tr[p].ch[1]);
    tr[p].rev ^= 1;
}

inline void pushdown(int p) {
    int lch = tr[p].ch[0], rch = tr[p].ch[1];
    if(tr[p].rev) {
        if(lch) reverse(lch);
        if(rch) reverse(rch);
        tr[p].rev ^= 1;
    }
}

int sta[MAXN], stop;

inline void pushto(int p) {
    stop = 0;
    while(!isroot(p)) {
        sta[stop++] = p;
        p = tr[p].fa;
    }
    sta[stop++] = p;
    while(stop) {
        pushdown(sta[--stop]);
    }
}

inline void rotate(int p) {
    bool t = !isleft(p); int fa = tr[p].fa, ffa = tr[fa].fa;
    tr[p].fa = ffa; if(!isroot(fa)) tr[ffa].ch[!isleft(fa)] = p;
    tr[fa].ch[t] = tr[p].ch[!t]; tr[tr[fa].ch[t]].fa = fa;
    tr[fa].fa = p; tr[p].ch[!t] = fa;
    update(fa);
}

inline void splay(int p) {
    pushto(p);
    for(int fa = tr[p].fa; !isroot(p); rotate(p), fa = tr[p].fa) {
        if(!isroot(fa)) rotate(isleft(p) == isleft(fa) ? fa : p);
    }
    update(p);
}

inline void access(int p) {
    for(int q = 0; p; q = p, p = tr[p].fa) {
        splay(p);
        tr[p].ch[1] = q;
        update(p);
    }
}

inline int findrt(int p) {
    access(p);
    splay(p);
    while(tr[p].ch[0]) p = tr[p].ch[0];
    return p;
}

inline void makert(int p) {
    access(p);
    splay(p);
    reverse(p);
}

inline void split(int u, int v) {
    makert(u);
    access(v);
    splay(v);
}

inline void link(int u, int v) {
    split(u, v);
    tr[u].fa = v;
}

inline void cut(int u, int v) {
    split(u, v);
    if(tr[v].ch[0] != u || tr[u].ch[1]) return;
    tr[v].ch[0] = tr[u].fa = 0;
}

inline int query(int u, int v) {
    split(u, v);
    return tr[v].mx;
}

int n, m, ans = INF;

inline void updateans(int a) {
    if(findrt(1) == findrt(n)) {
        ans = std::min(ans, a + tr[query(1, n)].val);
    }
}

struct Edge {
    int u, v, a, b;
    inline bool operator<(const Edge &rhs) const {
        return a < rhs.a;
    }
} edge[MAXN];

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= m; i++) {
        edge[i].u = readint(); edge[i].v = readint();
        edge[i].a = readint(); edge[i].b = readint();
    }
    std::sort(edge + 1, edge + m + 1);
    for(int i = 1; i <= m; i++) {
        int u = edge[i].u, v = edge[i].v, a = edge[i].a, b = edge[i].b, 
            urt = findrt(u), vrt = findrt(v);
        if(urt == vrt) { // alrealy connected
            int t = query(u, v);
            if(tr[t].val > b) {
                cut(t, edge[t - n].u);
                cut(t, edge[t - n].v);
            } else {
                updateans(a);
                continue;
            }
        } 
        tr[i + n].val = b; tr[i + n].mx = i + n;
        link(u, i + n); link(v, i + n);
        updateans(a);
    }
    printf("%d", ans != INF ? ans : -1);
    return 0;
}