题意

传送门:洛谷 P3231 - 消毒

给你一个三维点集 \(S\),令 \(L_p(S) = \max_{i, j \in S} |p_i - p_j|\),你要把它分成若干个子集 \(T\),使得 \(\sum_{i \in T} \min\{L_x(i), L_y(i), L_z(i)\}\) 尽可能小。

建议结合原题题意理解题目。为了方便,题解部分将会混用两种描述方式。

保证对于每个点 \((x, y, z)\),均有 \(x \le a, y \le b, z \le c\),且 \(abc \le 5000\)

阅读全文 »

简介

给你 \(n\) 个布尔未知数,有 \(m\) 条限制,每条限制与一对变量有关(如 \(a \lor b = \operatorname{true}\))。求一组满足所有限制的可行解。

阅读全文 »