题面
有 \(n\) 种颜色的球，第 \(i\) 种颜色的球有 \(a_i\) 个，有 \(m\) 个盒子，第 \(i\) 个盒子能装 \(b_i\) 个球，第 \(i\) 个颜色的球在第 \(j\) 个盒子中最多装 \(ij\) 个，求最多能装多少个球。
\(n\le 500,m\le 5\times 10^5 a_i,b_i\le 10^{13}\) 。
题解
要注意到这是个网络流模型：
- \(S\to i\)，流量为 \(a_i\)，记为 \(A\) 类边。\(n+j\to T\) ，流量 \(b_i\) ，\(B\) 类边。\(i\to n+j\) 流量 \(ij\)，\(C\) 类边
然后我们考虑最小割！
在 \(1\sim n\) 中我们选出一些点组成 \(S\) ，这些点割 \(A\) 类边，记 \(k=\sum_{x\in S}x\)。
那么对于一个右边的点，如果割 \(B\) 类边费用是 \(b_i\) ，割 \(C\) 类边费用就是 \(i\times k\) 。
那我们就可以从小到大枚举 \(k\) ，用dp算出 \(\min\{\sum_{x\in S}a_x|k=\sum_{x\in S}x\}\) ，然后就可以处理出 \(\sum_{i=1}^m\min(ik,b_i)\) 了
类似的题还有ARC125E，当时竟然没有写题解...
启发
- 一类特殊二分图的模拟网络流问题。