魔法森林问题

解题思路

本题给我们一个无向图，存在重边和自环。图中每条边存在两个权值 $a_i$ 和 $b_i$，要求我们求出从 $1$ 到 $n$ 的权值最小路径。

权值最小路径并不是最短路，对于每条路径，它的权值是该路径上经过的所有边的 $a_i$ 的最大值加上 $b_i$ 的最大值。（$a_i$ 的最大值和 $b_i$ 的最大值不一定在同一条边上）

可以发现每条路径的权值都取决于两个属性各自的最大值，显然我们并没有一个很好的方法把两个信息同时来做，而由于两个属性在路径中都是完全独立、互不相关的，因此我们可以考虑将他们分开。

我们可以将某一个属性的最大值固定，这样只需要去求另一个属性最大值的最小值即可，最多 $m$ 条边，因此一个属性的最大值只有 $m$ 个，所以可以直接枚举，这里将 $a$ 的最大值固定，枚举 $a_i$ 是路径中的最大值时，我们求一下 $b$ 的最大值最小是多少。这时候情况就比较固定了。

当路径中的最大值是 $a_i$ 时，就意味我们只能用 $a$ 的权值 $\leq a_i$ 的边，在这个前提下我们要找到一条从 $1$ 到 $n$ 的路径，使得路径中 $b$ 的最大值最小。

为了方便实现图中只存在 $a$ 权值 $\leq a_i$ 的边，我们可以先将 $a$ 排序，然后从小到大枚举 $a$ 的最大值，这样枚举的能保证图中的边应该是按照权值依次增加的，因此我们可以在枚举到 $a_j$ 为最大值时，动态的将 $a_j$ 这条边加入图中，而每次加入边之后，我们都要求一下当前从 $1$ 到 $n$ 的 $b$ 的权值最大值最小的路径，假设此时 $b$ 的最大值最小是 $b_j$，那么在 $a_j$ 为最大值时，路径的最小权值就是 $a_j+b_j$，用这个权值更新一下我们的答案。当枚举完所有 $a_j$，就能得到所有路径的最小权值。

要想能动态加边的同时处理一些树上路径的信息，很显然就要用到动态树来做，但是本题是一张图，图中可能存在重边和自环，因此我们在加边的时候可能加出一个环，而动态树只能处理树的问题，不能处理环。因此在加上一条边之后会出现环时，此时我们就需要去掉环上的某一条边来保证无环，为了让最大的权值最小，贪心的考虑就是要去掉环中权值最大的一条边，假设当前要在 $(u, v)$ 之间加边，如果当前 $(u, v)$ 不连通，直接加边，如果连通，说明加上后会出现环，因此找出 $u$ 到 $v$ 的路径上权值最大的边，若这条边的权值比 $(u, v)$ 的权值小，那么 $(u, v)$ 就不用加入，若这条边的权值比 $(u, v)$ 的权值大，那么就将这条边删去，再加入 $(u, v)$，这样我们就能保证维护的永远是一个森林，不会存在环。

通过刚才的分析，发现我们不止要进行加边和删边的操作，还要查询某一条路径上的权值最大值，这一步就可以在 $Splay$ 中动态的维护区间最大值即可。

以上思路就能实现本题的全部操作，但是这里还有一个问题，本题的权值都是在边上而不是在点上，但是在 $Link\_Cut\_Tree$ 中 $Splay$ 维护的是点不是边，这里需要用到一个将边权转化成点权的常用技巧，假设当前边为 $(u, v)$，我们加入一个新点 $x$，将原本 $u$ 和 $v$ 相连的结构变成 $u$ 和 $x$ 相连，$x$ 和 $v$ 相连，然后将 $(u, v)$ 边上的权值放到 $x$ 上，这样就能在不影响树的结构的前提下将边权转化为点权。然后本题保证所有边权都是 $> 1$ 的，所以我们将所有不是边转化的点的权值设为 $0$ 即可，由于我们要找的都是权值最大值，因此 $0$ 是不可能被取到的。

另外本题在时间上有点卡常，而 $Link\_Cut\_Tree$ 的 $find\_root(x)$ 这个函数太慢了，所以我们用这个函数来判断连通性时效率非常低，因此我们可以改用并查集来维护连通性。

本题一共 $m$ 个操作，每个操作都是在动态树上的一些处理，动态树的时间复杂度是 $O(logm)$ 的，因此整个算法的时间复杂度为 $O(mlogm)$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 150010, INF = 0x3f3f3f3f;

struct Edge
{
    int x, y, a, b;
    bool operator< (const Edge &t) const //按 a 从小到大排序
    {
        return a < t.a;
    }
}edges[N]; //存储每条边的信息

struct Node
{
    int s[2], p, v; //子节点、父节点、权值
    int mx, rev; //所在子树中的权值最大的点的编号、子节点是否需要翻转（懒标记）
}tr[N]; //Splay
int stk[N]; //辅助栈，用于下传懒标记

int n, m;
int p[N]; //并查集

int find(int x) //返回 x 所在集合的根节点
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void pushrev(int x) //翻转 x
{
    swap(tr[x].s[0], tr[x].s[1]);
    tr[x].rev ^= 1;
}

void pushup(int x) //从子节点的信息更新当前节点的信息
{
    tr[x].mx = x;
    for(int i = 0; i < 2; i++)
        if(tr[tr[x].mx].v < tr[tr[tr[x].s[i]].mx].v)
            tr[x].mx = tr[tr[x].s[i]].mx;
}

void pushdown(int x) //将当前节点的懒标记下传给子节点
{
    if(tr[x].rev)
    {
        pushrev(tr[x].s[0]), pushrev(tr[x].s[1]);
        tr[x].rev = 0;
    }
}

bool is_root(int x) //判断 x 是不是所在 Splay 的根节点
{
    return tr[tr[x].p].s[0] != x && tr[tr[x].p].s[1] != x;
}

void rotate(int x) //左旋、右旋
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    if(!is_root(y)) tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

void splay(int x) //将 x 转到根节点
{
    //将 x 转上去之前先将懒标记传下来
    int top = 0, r = x;
    stk[++top] = r;
    while(!is_root(r)) stk[++top] = r = tr[r].p;
    while(top) pushdown(stk[top--]);

    while(!is_root(x))
    {
        int y = tr[x].p, z = tr[y].p;
        if(!is_root(y))
        {
            if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}

void access(int x) //建立一条从根节点到 x 的实边路径，并将 x 转到所在 Splay 的根节点
{
    int z = x;
    for(int y = 0; x; y = x, x = tr[x].p)
    {
        splay(x);
        tr[x].s[1] = y;
        pushup(x);
    }
    splay(z);
}

void make_root(int x) //将 x 变成整棵树的根节点，并将 x 转到所在 Splay 的根节点
{
    access(x);
    pushrev(x);
}

int find_root(int x) //找到 x 所在实边路径的根节点，并将 x 所在实边路径的根节点转到其所在 Splay 的根节点
{
    access(x);
    while(tr[x].s[0]) pushdown(x), x = tr[x].s[0];
    splay(x);
    return x;
}

void split(int x, int y) //建立一条从 x 到 y 的实边路径，实边路径对应的 Splay 的根节点是 y
{
    make_root(x);
    access(y);
}

void link(int x, int y) //如果 x 和 y 不连通，则在 x 和 y 之间加入一条边（虚边）
{
    make_root(x);
    if(find_root(y) != x) tr[x].p = y;
}

void cut(int x, int y) //如果 x 和 y 之间存在边，则将该边删去
{
    make_root(x);
    if(find_root(y) == x && tr[y].p == x && !tr[y].s[0])
    {
        tr[x].s[1] = tr[y].p = 0;
        pushup(x);
    }
}

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= m; i++)
    {
        int x, y, a, b;
        scanf("%d%d%d%d", &x, &y, &a, &b);
        edges[i] = {x, y, a, b};
    }

    sort(edges + 1, edges + 1 + m); //将所有边按照 a 的权值从小到大排序

    //1 ~ n 表示普通点的编号，n + 1 ~ m 表示边对应的点的编号
    for(int i = 1; i <= n + m; i++)
    {
        p[i] = i; //初始化并查集

        //初始化 Splay
        if(i > n) tr[i].v = edges[i - n].b; //代表边的点赋上对应的权值
        tr[i].mx = i; //每个点最开始权值最大值都是自己
    }

    int res = INF; //记录答案
    for(int i = 1; i <= m; i++) //按照 a 的权值从小到大枚举每条边
    {
        int x = edges[i].x, y = edges[i].y, a = edges[i].a, b = edges[i].b;
        if(find(x) == find(y)) //如果 x 和 y 连通 
        {
            split(x, y); //建立一条从 x 到 y 的实边路径，实边路径对应的根节点是 y
            int t = tr[y].mx; //记录 x 到 y 路径上权值最大的点
            if(tr[t].v > b) //如果 t 的权值 > b
            {
                //此时需要将 t 对应的边删掉，再将当前这条边加上
                cut(edges[t - n].x, t), cut(t, edges[t - n].y);
                link(x, n + i), link(n + i, y);
            }
        }
        else //如果 x 和 y 不连通
        {
            //直接将当前这条边加入
            p[find(x)] = find(y); //更新并查集
            link(x, n + i), link(n + i, y); //加入边
        }

        //如果 1 和 n 连通
        if(find(1) == find(n))
        {
            split(1, n); //建立一条从 1 到 n 的实边路径，实边路径对应的根节点是 n
            res = min(res, a + tr[tr[n].mx].v); //更新答案
        }
    }

    if(res == INF) res = -1; //如果无解则输出 -1
    printf("%d\n", res);

    return 0;
}