AGC031E 题解

首先一件珠宝的选取与否无法同时对四个限制作出回应，所以单纯以网络流上的一个节点代表一个珠宝是否选取是行不通的。于是可以考虑对所有横坐标以及纵坐标分别建图。设坐标为 $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)$。