ARC142E 题解

shiruoyu114514 · 2025-05-20 19:48:23 · 题解

首先对于一对限制 (x,y)，形象来说就是能不能将 a_x,a_y 与 b_x,b_y 配对，使得 a_x \ge b_{tox}，a_y \ge b_{toy}。也即 \min(a_x,a_y) \ge \min(b_x,b_y)，\max(a_x,a_y) \ge \max(b_x,b_y)。即两个数都 \ge \min(b_x,b_y)，至少有一个数 \ge \max(b_x,b_y)。于是就可以首先把 a_x,a_y 对 \min(b_x,b_y) chkmax。

现在的限制就是 a_x,a_y 至少有一个 \ge \max(b_x,b_y)。考虑最小割：我们尝试把每个点拆成 p_{i,j}。对于每个点，其与 S 连通时，a_i \ge j。当加边 (p_{i,v_1},p_{j,v_2},\infty) 时，则有限制：当 a_i \ge v_1 时，a_j \ge v_2。整张图额外连接 (p_{i,v_1},p_{i,v_1+1},p_{i,v_1}-a_{i0})，即确立选择一个权值的代价。连接 (p_{i,v_1+1},p_{i,v_1},+\infty) 以避免一条链上割两个点。

但是本题需要的约束可是 a_i <v_1 时，a_j \ge v_2。方向是反的。

要解决这个问题，你需要有一个惊人的注意力：如果 a_x \ge b_x 并且 a_y \ge b_y 的话不用管。在调整过后，不会有 a_x < b_x 且 a_y < b_y 的情况。所以我们考虑的所有点对都形如 a_x < b_x 且 a_y \ge b_y 的情况。发现 a_x 与 b_x 的大小关系本身就能将所有数分成两个确定的集合，这不是二分图吗？

考虑把所有 a_x < b_x 的点倒过来，即把 p_{x,v} 看成是 [a_x<v]。则一个连边 (p_{x,v_1},p_{y,v_2},+\infty) 则为如果 a_x<v_1，那么 a_y \ge v_2。非常契合限制。

跑一遍最小割即可。