AGC031E 题解

shiruoyu114514 · 2025-05-21 08:39:16 · 题解

首先一件珠宝的选取与否无法同时对四个限制作出回应，所以单纯以网络流上的一个节点代表一个珠宝是否选取是行不通的。于是可以考虑对所有横坐标以及纵坐标分别建图。设坐标为 x 的点为 c_x，则对于一个位于 (x,y)，价值为 v 的珠宝，建边 (c_x,c_y,1,v)。

如果每一维只有小于等于某坐标最多多少个的限制，那么大可以把每个坐标限制建一个点 p_x。流入该点的珠宝可以选择去往限制 p_{x-1} 以达到更小的坐标，或者直接兑现坐标为 x。具体地，假设小于等于 x 的至多 \lim_x 个点，那么就连接 (p_x,p_{x-1},\lim_{x-1},0)。特别地，需要连接 (S,p_n,\lim_n,0)，即代表至多有 \lim_n 个点通过此进入选择。除此之外，连接 (p_x,c_x,+\infty,0)，代表可以有任意个点选择 c_x 作为该维坐标。跑最大费用最大流即可。

但是现在的问题是同时具有 \le 型限制以及 \ge 型限制，显然一侧实点不可能两侧都处理坐标限制，因为它还要作为二分图上的一侧点，连接二分图上的另一侧点。

考虑将限制转化为坐标从小往大排序的第 x 个点的坐标 \ge 限制值。枚举选择的珠宝数量。显然我们可以解出坐标从小到大排序的第 x 个点的范围。考虑对于每一维重新建图，把 p_i 设定为从小到达第 i 个珠宝，其向其可以选择的坐标 x 连边 (p_i,c_x,1,0)。显然每一种合法方案都可以算上，而建图也恰好保证了所有方案都合法。于是跑最大费用最大流即可。

另一维同理。

总结一下建图：假设两维的珠宝点为 c_i,d_j，坐标点为 p_x,q_y，则有以下建图：

对于每一个 i 建立 (S,c_i,1,0)，对于每一个点 j 建立 (d_j,T,1,0)。

如果第 i 个珠宝的 x 坐标属于 [lx_i,rx_i]，那么对于每一个 i' \in [lx_i,rx_i] 建立 (c_i,p_{i'},1,0)。如果第 j 个珠宝的 y 坐标属于 [ly_j,ry_j]，那么对于每一个 j' \in [ly_j,ry_j] 建立 (q_{j'},d_j,1,0)。

如果有一个珠宝坐标为 (x,y,v)，那么建立 (p_x,q_y,1,v)。