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

题意

给出

n

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

思路

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

通过并查集处理出环，认定编号最小的点为还的根节点。
这时对于每个点就有两种情况，处在一个环中或者是独立的一个点（其实就是自环，因为每个点有且只有一个子节点）。
遍历一遍所有点，为每个点所处环的大小贡献 $+1$ ，统计出每个环的大小。
再遍历一遍，将每个环的大小传递到环上每一个点，这时，每个点就求出了不使用魔法能跑出的最长路（当然不能重复，像上文说的一样一直刷路径长度和）。
怎么使用魔法最优呢？这个答案很明显，还是遍历一遍，先判断相邻两个点是否在同一个环中，如果不在同一个环中就可以用魔法连接这两个点获得长度和。计算出最大答案即可。

求最长路小提示：

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

O(n^2)

。

所以很明显哈，因为每个点只有一个儿子，那么就不会出现走到一个点有多条路选择，同时这道题用的是并查集，那么可以在合并查找父亲点时为所有父节点

+1

，那么我们就可以在处理并查集的时候就计算出环的长度。

AC代码

CPP

#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 了这道题......。

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

文章操作

题意

思路

求最长路小提示：

AC代码

注意：

相关推荐

评论

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