3335. [USACO20 Jan Silver]虫洞排序

【题目描述】

Farmer John 的奶牛们已经厌倦了他对她们每天早上排好序离开牛棚的要求。她们刚刚完成了量子物理学的博士学位，准备将这一过程搞♂快点。

今天早上，如同往常一样，Farmer John 的 $N$ 头编号为 $1 \dots N$ 的奶牛（$1 \leq N \leq 10^5$），分散在牛棚中 $N$ 个编号为 $1 \dots N$ 的不同位置，奶牛 $i$ 位于位置 $p_i$。但是今天早上还出现了 $M$ 个编号为 $1 \dots M$ 的虫洞（$1 \leq M \leq 10^5$），其中虫洞 $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 ， … ， p_N $。保证$ p $在$ 1 … N $之间。

接下来$ M $行，每行包含三个整数$ a_i，b_i $和$ w_i $，保证每个$ i $在$ 1 $和$ M $之间。

【输出格式】

一个整数，即奶牛在排队过程中必须进入的最小虫洞的宽度的最大值。

如果奶牛不需要任何虫洞来分类，则输出-1。

【样例输入1】

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

【样例输出1】

9

【样例输入2】

4 1
1 2 3 4
4 2 13

【样例输出2】

-1

【样例解释】

【提示】

对于$ 30\% $的测试数据(测试点$ 3\sim5 $)，满足$ M,N ≤ 1,000 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 一月公开赛 Silver 组