奶牛排序
Description
<!DOCTYPE html> <html> <body>Farmer John 的奶牛们已经厌倦了他对她们每天早上排好序离开牛棚的要求。她们刚刚完成了量子物理学的博士学位，准备将这一过程搞快点。
今天早晨，像往常一样，Farmer John的N头奶牛（$1\leq N\leq 10^5$）（方便地编号为$1\sim N$）散布在整个谷仓中N个不同的位置，也编号为$1\sim N$，这样奶牛$i$位于$p_i$位置。但是今天早上还有M个虫洞（$1\leq M\leq 10^5$），编号为$1\sim M$，其中虫洞$i$双向将位置$a_i$与位置$b_i$连接起来，宽度为$w_i$（$1\leq a_i,b_i\leq N$，$a_i\neq b_i$，$1\leq w_i\leq 10^9$）。
在任何时间点，位于虫洞相对两端的两头奶牛都可以选择同时通过虫洞交换位置。奶牛必须进行这种互换，直到奶牛$i$在位置$i$处$1\leq i\leq N$。
奶牛不渴望被虫洞压扁。帮助他们最大化必须用于分类的最小虫洞的宽度。可以保证奶牛可以自己分类。
输入格式
第一行包含两个整数$N$和$M$。
第二行包含$N$个整数$p_1,p_2,\ldots,p_N$。 保证$p$是$1\sim 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
4 1
1 2 3 4
4 2 13
输出
9
-1
数据范围与提示
$50\%$的数据,$N,M\leq 1000$
样例一解释
母牛1和母牛2使用第三个虫洞互换位置。
母牛1和母牛3使用第一个虫洞互换位置。
母牛2和母牛3使用第三个虫洞互换位置。
样例二解释
无需使用虫洞
</body> </html>Source
并查集 USACO20JAN统计
相关
在下列比赛中: