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

zhuzhu2891 · 2025-09-30 20:10:03 · 题解

写一个非常简洁的 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) 的。