题解：P6898 [ICPC 2014 WF] Metal Processing Plant

写一个非常简洁的 $O(n^3)$ 做法。

考虑钦定 $D(A)\ge D(B)$，然后我们从大到小枚举 $D(A)$，并尝试找出最小的合法的 $D(B)$。

确定了一个 $D(A)$ 之后，判断一个 $D(B)$ 是否合法的方式是通过 2-sat，相当按照边权从大到小的顺序加入限制 $x\in B\rightarrow y\in A$ 直到某一时刻 2-sat 无解，无解时加入的边的边权就是 $D(B)$ 的最小值。

于是这其实相当于一个最大瓶颈路问题（最大化路径上边权的最小值）。

然后我们直接维护 $d_{i,j}$ 表示 $i$ 到 $j$ 路径上边权的最小值的最大值（注意这里的图是 2-sat 图即每个点拆成两半的图，初始时图中有所有形如 $x\in B\rightarrow y\in A$ 的边）。现在我们从大到小枚举 $D(A)$，每次只需要加入一个形如 $x\in A\rightarrow y\in B$ 的限制，然后可以 $O(n^2)$ 地更新整个 $d$ 数组。

然后有一个众所周知的事实就是只有 $O(n)$ 个 $D(A)$ 是有用的，我们发现我们其实也只需要加入 $O(n)$ 条形如 $x\in A\rightarrow y\in B$ 的限制，于是复杂度就是 $O(n^3)$ 的。