「HLOI2015」Magic

//这次貌似暴露省份了……

题目描述

Chavo 是一个生活在魔法世界里的小法师。魔法的世界里有 座法师塔，第 座法师塔有 点魔法。其中有 对法师塔之间可以相互传送，传送消耗的魔法值是两个法师塔魔法值的最小公倍数。

Chavo 想要从第一座法师塔传送到第 座法师塔，她在每一次传送之后都会等待魔法全部恢复再进行下一次传送，也就是说 Chavo 需要的魔法值只是所有传送消耗魔法的最大值。

Chavo 想知道她最少需要多少魔法值就可以从第一座法师塔传送到第 座法师塔？

输入

第一行输入整数 和 。

接下来一行 个数，第 个数 代表第 座法师塔的魔法值。

接下来 行，每行 个数 ，代表第 座法师塔和第 座法师塔之间可以相互传送。

输出

输出一行带有一个整数，代表需要的最小魔法值。

样例输入

3 3
2 3 5
1 3
3 1
2 2

样例输出

10

样例说明

只有一条路径从 到 ，传送需要的魔法值是 和 的最小公倍数 ，故需要 点魔法值。

数据范围及约定

对于 的数据，；

对于 的数据，；

对于 的数据，。

时间限制与空间限制

时间限制：，空间限制：。

题解

因为最大值符合加法性质（即两部分最大值的最大值为整体最大值），所以可以类似 SPFA 一样松弛。

应该是这样吧，题解打的是二分套 SPFA 验证。

根据题目，求的是两点之间的路径长度最大值的最小值，考虑货车运输的类似做法即可，不过货车运输求的是两点之间路径长度最小值的最大值。

直接 SPFA 的时间复杂度是 的，标程的时间复杂度是 的，最小生成树的时间复杂度是 的。

逆天 std，这就一个 到 的最小瓶颈路，做个最小生成树，然后找一下 到 的最大边权就行了。

代码见这里。