AcWing 999. 魔法森林 题解

题目分析

本题中，小E要从(1)号节点出发，经过一个包含(n)个节点、(m)条边的无向图（魔法森林）到达(n)号节点拜访隐士。每条边有两个权值(a_i)和(b_i)，小E携带的(A)型守护精灵个数不少于(a_i)且(B)型守护精灵个数不少于(b_i)时，才能安全通过这条边。需要求出小E成功拜访到隐士最少需要携带的守护精灵总个数，若无法到达则输出(-1)。

解题思路

本题采用动态加点的最小生成树（Kruskal）结合树链剖分（这里用LCT，即Link - Cut Tree，动态树）的方法求解。先将边按照权值(a)从小到大排序，然后依次加入边，利用LCT维护连通性和路径上的最大(b)值，通过不断更新最小的守护精灵总个数来得到最终结果。

代码逐段分析

1. 头文件和全局变量定义

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

using namespace std;

const int N = 150010, INF = 1e8;

int n, m;
struct Edge
{
    int x, y, a, b;
    bool operator< (const Edge& t) const
    {
        return a < t.a;
    }
}e[N];
struct Node
{
    int s[2], p, v;
    int mx, rev;
}tr[N];
int stk[N], p[N];

• 引入必要的头文件，iostream用于输入输出，cstring用于字符串操作，algorithm用于排序等算法。
• 定义常量(N)（最大边数和节点数之和）和(INF)（无穷大）。
• 变量(n)表示节点数，(m)表示边数。
• Edge结构体用于存储边的信息，包括两个端点(x)、(y)以及权值(a)、(b)，并重载小于运算符，方便按照权值(a)对边进行排序。
• Node结构体用于LCT中节点的信息存储，s[2]表示左右子节点，p表示父节点，v表示节点权值（这里对应边的(b)值），mx表示以该节点为根的子树中权值最大的节点编号，rev用于标记该子树是否需要翻转。

• stk数组用于在LCT操作中存储路径上的节点，p数组用于并查集操作，存储每个节点的父节点。

• 并查集相关函数

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

查找节点(x)在并查集中的根节点，同时进行路径压缩，使后续查找更高效。

1. LCT相关辅助函数

void pushrev(int 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[tr[x].s[i]].mx].v > tr[tr[x].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;
    }
}

• pushrev函数用于翻转节点(x)的左右子树，并更新翻转标记。
• pushup函数用于更新节点(x)的mx值，使其指向以(x)为根的子树中权值最大的节点。

• pushdown函数用于将节点(x)的翻转标记下传至其子节点，并清除该标记。

• LCT相关判断和操作函数

bool isroot(int x)
{
    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 (!isroot(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)
{
    int top = 0, r = x;
    stk[ ++ top] = r;
    while (!isroot(r)) stk[ ++ top] = r = tr[r].p;
    while (top) pushdown(stk[top -- ]);
    while (!isroot(x))
    {
        int y = tr[x].p, z = tr[y].p;
        if (!isroot(y))
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
}

• isroot函数用于判断节点(x)是否为所在Splay树的根节点。
• rotate函数实现对节点(x)的旋转操作，以维护LCT的性质。

• splay函数将节点(x)旋转到所在Splay树的根节点位置，在旋转前先将路径上的节点标记下传。

• LCT的核心操作函数

void access(int x)
{
    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 makeroot(int x)
{
    access(x);
    pushrev(x);
}

int findroot(int x)
{
    access(x);
    while (tr[x].s[0]) pushdown(x), x = tr[x].s[0];
    splay(x);
    return x;
}

void split(int x, int y)
{
    makeroot(x);
    access(y);
}

void link(int x, int y)
{
    makeroot(x);
    if (findroot(y) != x) tr[x].p = y;
}

void cut(int x, int y)
{
    makeroot(x);
    if (findroot(y) == x && tr[y].p == x && !tr[y].s[0])
    {
        tr[x].s[1] = tr[y].p = 0;
        pushup(x);
    }
}

• access函数将节点(x)到根节点的路径变为一条链，同时更新相关节点信息。
• makeroot函数将节点(x)变为所在树的根节点，通过先access再翻转实现。
• findroot函数查找节点(x)所在树的根节点，先access再不断向左子树寻找。
• split函数将节点(x)和(y)置于同一棵树中，并将(x)变为根节点，(y)变为链的末端。
• link函数连接节点(x)和(y)，若它们不在同一棵树中则建立连接。

• cut函数切断节点(x)和(y)之间的连接，前提是它们在同一棵树中且满足特定条件。

• 主函数

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);
        e[i] = {x, y, a, b};
    }
    sort(e + 1, e + m + 1);

• 读取节点数(n)和边数(m)。
• 读取每条边的信息，存储在e数组中。
• 将边按照权值(a)从小到大排序。

    for (int i = 1; i <= n + m; i ++ )
    {
        p[i] = i;
        if (i > n) tr[i].v = e[i - n].b;
        tr[i].mx = i;
    }

初始化并查集的父节点数组p，对于代表边的节点（编号大于(n)），设置其权值为对应边的(b)值，并初始化每个节点的mx为自身。

    int res = INF;
    for (int i = 1; i <= m; i ++ )
    {
        int x = e[i].x, y = e[i].y, a = e[i].a, b = e[i].b;
        if (find(x) == find(y))
        {
            split(x, y);
            int t = tr[y].mx;
            if (tr[t].v > b)
            {
                cut(e[t - n].x, t), cut(t, e[t - n].y);
                link(x, n + i), link(n + i, y);
            }
        }
        else
        {
            p[find(x)] = find(y);
            link(x, n + i), link(n + i, y);
        }

• 初始化结果变量res为无穷大。
• 遍历每条边：
  • 如果边的两个端点在同一连通分量中（通过并查集判断）：
    • 使用split函数将(x)和(y)置于同一棵树中，并将(x)变为根节点。
    • 找到路径上权值最大的节点(t)。
    • 如果该节点权值大于当前边的(b)值，切断原来的边，连接新的边。
  • 如果边的两个端点不在同一连通分量中：
    • 在并查集中合并两个连通分量。
    • 在LCT中连接对应的节点。

        if (find(1) == find(n))
        {
            split(1, n);
            res = min(res, a + tr[tr[n].mx].v);
        }
    }
    if (res == INF) res = -1;
    printf("%d\n", res);

    return 0;
}

• 如果(1)号节点和(n)号节点在同一连通分量中：
  • 使用split函数将(1)和(n)置于同一棵树中，并将(1)变为根节点。
  • 更新最小守护精灵总个数res。
• 如果最终res仍为无穷大，说明无法到达，将其设为(-1)。
• 输出结果res。

时间复杂度分析

• 对边进行排序的时间复杂度为(O(m log m))。
• 遍历每条边进行并查集和LCT操作，每次操作的时间复杂度为(O(log n))，总共(m)条边，所以这部分时间复杂度为(O(m log n))。
• 总的时间复杂度为(O(m log m + m log n))，近似为(O(m log m))。

空间复杂度分析

• 存储边的数组e占用(O(m))的空间。
• LCT相关的节点数组tr、并查集数组p等占用(O(n + m))的空间。
• 总的空间复杂度为(O(n + m))。