P6915: 虫洞排序
传统题
1.000s
时间限制
256MB
内存限制
0 提交
0 解决
【题目描述】
【题目描述】
Farmer John
的奶牛们已经厌倦了他对她们每天早上排好序离开牛棚的要求。她们刚刚完成了量子物理学的博士学位，准备将这一过程搞快点。
今天早上，如同往常一样，Farmer John
的 N 头编号为 1…N 的奶牛（1≤N≤10^5
），分散在牛棚中 N
个编号为 1…N 的不同位置，奶牛 i 位于位置 pi。但是今天早上还出现了 M
个编号为 1…M 的虫洞（1≤M≤10^5
），其中虫洞 i
双向连接了位置 ai 和 bi，宽度为 wi
（1≤ai,bi≤N,ai≠bi,1≤wi≤10
^9
）。
在任何时刻，两头位于一个虫洞两端的奶牛可以选择通过虫洞交换位置。奶牛们需要反复进行这样的交换，直到对于 1≤i≤N
，奶牛 i
位于位置 i。
奶牛们不想被虫洞挤坏。帮助她们最大化被她们用来排序的虫洞宽度的最小值。保证奶牛们有可能排好序。
输入格式（文件名：wormsort.in
）：
输入的第一行包含两个整数 N
和 M。
第二行包含 N
个整数 p1,p2,…,pN。保证 p
是 1…N 的一个排列。
对于 1
到 M 之间的每一个 i，第i+2
行包含整数 ai、bi
和 wi。
【
输出格式】
（文件名：wormsort.out
）：
输出一个整数，为在排序过程中奶牛必须挤进的虫洞的最小宽度的最大值。如果奶牛们不需要用任何虫洞来排序，输出 −1
。
【
输入样例】
：
4 4
3 2 1 4
1 2 9
1 3 7
2 3 10
2 4 3
【
输出样例】
：
9
【样例说明】
以下是一个仅用宽度至少为 9
的虫洞给奶牛排序的可能方案：
1.奶牛 1
和奶牛 2 使用第三个虫洞交换位置。
2.奶牛 1
和奶牛 3 使用第一个虫洞交换位置。
3.奶牛 2
和奶牛 3 使用第三个虫洞交换位置。
【
输入样例】
：
4 1
1 2 3 4
4 2 13
【
输出样例】
：
-1
【样例说明】
给奶牛们排序不需要使用任何虫洞。
【
测试点性质】
：
测试点 3-5
满足 N,M≤1000。
测试点 6-10
没有额外限制。