Wormhole Sort

题目描述

农夫约翰的奶牛们已经厌倦了他每天早晨要求她们在离开牛棚前把自己排好序的请求。她们刚刚完成了量子物理博士学位，准备把事情加快一点。 今天早晨，和往常一样，农夫约翰有 $N$ 头奶牛（$1 \leq N \leq 10^5$），方便起见编号为 $1\dots N$。她们分散在牛棚中 $N$ 个互不相同的位置上，这些位置也编号为 $1\dots N$，并且奶牛 $i$ 位于位置 $p_i$。但今天早晨还有 $M$ 个虫洞（$1 \leq M \leq 10^5$），编号为 $1\dots M$：虫洞 $i$ 双向连接位置 $a_i$ 与位置 $b_i$，其宽度为 $w_i$ （$1\le a_i,b_i\le N, a_i\neq b_i, 1\le w_i\le 10^9$）。 在任意时刻，位于某个虫洞两端的两头奶牛可以选择同时通过该虫洞交换位置。奶牛们必须进行这样的交换，直到对所有 $1 \leq i \leq N$ 都满足奶牛 $i$ 位于位置 $i$。 奶牛们不想被虫洞挤扁。请帮助她们在完成排序所必须使用的虫洞中，使“最窄虫洞”的宽度尽可能大。 保证奶牛们一定可以完成排序。

输入格式

第一行包含两个整数 $N$ 和 $M$。 第二行包含 $N$ 个整数 $p_1, p_2, \dots, p_N$。保证 $p$ 是 $1\ldots N$ 的一个排列。 对于每个 $1$ 到 $M$ 的 $i$，第 $i+2$ 行包含整数 $a_i$、$b_i$ 和 $w_i$。

输出格式

输出一个整数：在排序过程中奶牛必须钻过的虫洞中，最小宽度的最大可能值。 如果奶牛们不需要使用任何虫洞就能完成排序，输出 $-1$。

4 4
3 2 1 4
1 2 9
1 3 7
2 3 10
2 4 3

9

4 1
1 2 3 4
4 2 13

-1

提示

评分： 测试点 3-5 满足 $N,M\le 1000.$ 测试点 6-10 没有额外限制。 下面是一种只使用宽度至少为 9 的虫洞来给奶牛排序的可能方法： 奶牛 1 和奶牛 2 使用第三个虫洞交换位置。 奶牛 1 和奶牛 3 使用第一个虫洞交换位置。 奶牛 2 和奶牛 3 使用第三个虫洞交换位置。 不需要任何虫洞就能将奶牛排好序。 题目致谢：Dhruv Rohatgi

标签: USACO|2020|Silver

来源

USACO|2020|Silver