P12123 [蓝桥杯 2024 省 B 第二场] 传送阵

· · 题解

题意

给出 n 个点之间的关系：每个点只指向一个下一个点，即每个点只有一个儿子（有可能是自己——自环）。问如何走能有最长路径，其中可以任意的从一个点跳到相邻的另一个点。

思路

题意很简单，就是需要知道从哪个点开始走的最长路最长，不可以重复的走同一个点，因为在正权图中可以通过一个环无限的刷长度和。其中可以从一个点跳跃到相邻的另一个点。从题目可以得出——每个传送阵一定且只能传送到另一个指定的传送阵

  1. 通过并查集处理出环，认定编号最小的点为还的根节点。

  2. 这时对于每个点就有两种情况，处在一个环中或者是独立的一个点（其实就是自环，因为每个点有且只有一个子节点）。

  3. 遍历一遍所有点，为每个点所处环的大小贡献 +1，统计出每个环的大小。

  4. 再遍历一遍，将每个环的大小传递到环上每一个点，这时，每个点就求出了不使用魔法能跑出的最长路（当然不能重复，像上文说的一样一直刷路径长度和）。

  5. 怎么使用魔法最优呢？这个答案很明显，还是遍历一遍，先判断相邻两个点是否在同一个环中，如果不在同一个环中就可以用魔法连接这两个点获得长度和。计算出最大答案即可。

求最长路小提示：

相信应该不会有可爱滴憨憨会在这道题用 SPFA 这种能跑最长路的算法来求最长路吧！用这些算法如何处理特殊的那条边呢？暴力枚举处理包会炸的！ O(n^2)。

所以很明显哈，因为每个点只有一个儿子，那么就不会出现走到一个点有多条路选择，同时这道题用的是并查集，那么可以在合并查找父亲点时为所有父节点 +1，那么我们就可以在处理并查集的时候就计算出环的长度。

AC代码

#include<cstdio>
#include<queue>
#include<algorithm>

using namespace std;

const int maxn = 1e6 + 5;

struct Edge {
    int u, v, next;
} e[maxn];

int n, a[maxn];
int ans, fa[maxn];
void Init() {
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
}

int Find(int x) {
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = Find(fa[x]);
}

void Input() {
    scanf("%d", &n);
    Init();
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        int root_a = Find(i), root_b = Find(a[i]);
        if (root_a != root_b) {                     //并查集模板：合并节点
            fa[i] = fa[a[i]];
        }
    }
    for (int i = 1; i <= n; ++i) {                  //额外再跑一遍让环内所有点直接连到根节点（个人代码风格，和题目无关）
        Find(i);                                    /*这样可以使fa[i]直接指向i的根节点，和 在用的时候再调用Find(i)一样滴~*/ 
    }
}

int Size[maxn];                                     //记录所有点的最长路长度 
void Sol() {
    for (int i = 1; i <= n; ++i) {                  //累加根节点的最长路长度 
        ++Size[fa[i]];
    }

    for (int i = 1; i <= n; ++i) {                  //先只计算最长路最大的单个环（不使用"魔法"） 
        ans = max(ans, Size[i]);
    }
    for (int i = 1; i < n; ++i) {                   //然后按照题目要求计算：最大相邻的两个环最长路的和 
        if (fa[i] != fa[i + 1]) {
            ans = max(ans, Size[fa[i]] + Size[fa[i + 1]]);
        }
    }
}

int main() {
    Input();
    Sol();
    printf("%d", ans);
    return 0;
}

注意：

题目中使用魔法有限制，只能从 j 直接跳到 j+1/j-1。

但是由于本题数据极水，直接取最长路最大的两个环最长路之和就能过，希望加强数据，因为同学就那样 AC 了这道题......。