网络流
1.
题意
在二维平面上，有 \(n\) 颗珠宝，第 \(i\) 颗珠宝在 \((x_i,y_i)\) 的位置，价值为 \(v_i\)。
现在有一个盗贼想要偷这些珠宝。
现在给出 \(m\) 个限制约束偷的珠宝，约束有以下四种：
- 横坐标小于等于 \(a_i\) 的珠宝最多偷 \(b_i\) 颗。
- 横坐标大于等于 \(a_i\) 的珠宝最多偷 \(b_i\) 颗。
- 纵坐标小于等于 \(a_i\) 的珠宝最多偷 \(b_i\) 颗。
- 纵坐标大于等于 \(a_i\) 的珠宝最多偷 \(b_i\) 颗。
现在问你在满足这些约束的条件下，盗贼偷的珠宝的最大价值和是多少。
- $1\leq N\leq80 $
- $1\leq x_i,y_i\leq100 $
- \(1\leq M\leq320\)
题解
限制很复杂，看起来无法贪心，可以想到网络流。
用这四种限制直接建模会发现无法将限制体现出来。
考虑将限制转化一下，以第一个为例，可以理解为横坐标从小到大排序后偷的第 \(b_i + 1\) 颗的横坐标大于 \(a_i\)，另外三个条件同理。现在还是存在四个限制，网络流不好处理。注意到 \(N\) 非常小，可以枚举偷的个数 \(k\)，将横坐标和纵坐标的限制分别统一。现在只剩两个限制:
- 横坐标排序后选的第 \(i\) 个点横坐标在 \([lx_i,rx_i]\) 内。
- 纵坐标排序后选的第 \(i\) 个点纵坐标在 \([ly_i,ry_i]\) 内。
此时建模，将原本的 \(N\) 个点拆点以限制只能偷一次和赋权值，左边加 \(k\) 个点表示横坐标排序后的第 \(i\) 个选择，右边加 \(k\) 个点表示纵坐标排序后的第 \(i\) 个选择，向满足上面的两种限制的中间的点连边。左右再分别和源汇点连起来。
- 左边的第 \(i\) 个点和右边的第 \(i\) 个点并不是同一个点，只是分别代表中间选择的点在关于横纵坐标排序后的排名。
- 不需要考虑新加的 \(k\) 个点中第 \(i\) 个点和第 \(i+1\) 个点选择的坐标大小关系，因为如果第 \(i\) 个点选择的横坐标比第 \(i+1\) 个点大，那么将选择的两个点交换后依然满足条件，故并没有多出新的情况。
最后这两条在自己看题解的时候想了好久。。。