坐标前后限制转点的坐标取值+网络流拆维拆点：agc031_e

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135075877

https://vj.imken.moe/contest/598718#problem/J

观察到数据范围很小，但一个很重要的信息我们缺失了，就是珠宝的数量，所以我们考虑枚举珠宝的数量 $k$ 。

对于横纵坐标什么至多至少的限制，比如 $a_i$ 前最多偷 $b_i$ 个，可以转化为第 $[b_i+1,k]$ 的坐标取值下界为 $a_i+1$ 。因此我们可以转化出在某个维度上第 $i$ 个宝石的取值范围是 $[L_i,R_i]$ 。

但是我们有两个维度，但我们刚好有两个源汇点，考虑拆维。左边维护 $x$ ，右边维护 $y$ 。

关于每个宝石只能选一个，还要使代价最大，我们在中间拆点，连 $(1,val)$ 的边，最后求一次费用流即可。