题解

思路

固定一个候选值 $X$。

做法

权值小于 $X$ 的边两端必须异色，因此这些边组成的子图必须是二分图；同一连通块内的染色也随之确定。连接同色顶点的最短违规路径只需考虑两条相邻边，因为更长路径的边权均为正，而任意两条相邻的小权边的两端在二分染色下同色。因此答案还不能超过任一顶点所连两条最小边权之和。将边按权值从小到大加入，用带奇偶关系的并查集维护二分图，第一次产生奇环时的边权就是二分性给出的上界，答案为它与上述两边权和最小值的较小者。

复杂度

排序需要 $O(M\log M)$ 时间，并查集合并近似为线性时间；总时间复杂度为 $O(M\log M)$，空间复杂度为 $O(N+M)$。所有边权和使用 64 位整数保存。