网络流之广义切糕模型

问题

有 \(n\) 个整数变量 \(x_i\)。\(x_i\) 可以取 \([1,m]\)，取 \(j\) 需要 \(a_{i,j}\) 的代价。有若干个约束，形如 \(x_{u_i} \le x_{v_i} + w_i\)。给变量赋值，最小化总代价。

建模

考虑求最小割。对每个整数变量拆 \(m+1\) 个点 \(p_{i,1},p_{i,2},\dots,p_{i,m+1}\)，连 \(n\) 条链 \(S \to p_{i,1} \to p_{i,2} \to \cdots \to p_{i,m} \to p_{i,m+1} \to \infty\)，其中 \(S \to p_{i,1}\) 和 \(p_{i,m+1} \to T\) 的容量为 \(\infty\)（表示不能割这条边），\(p_{i,j} \to p_{i,j+1}\) 的容量为 \(a_{i,j}\)。然后 \(p_{v_i,j+w_i} \to p_{u_i,j}\)，容量为 \(\infty\)，表示强制让 \(S\) 和 \(p_{v_i,j+w_i}\) 与 \(p_{u_i,j}\) 和 \(T\) 的连通关系不同。如果选了不合法的方案，那么 \(S \to T\) 还能经过这条边，就不是最小割了。

例题

1. 洛谷 P3227 [HNOI2013]切糕

由于对称性，只需考虑 \(f(x,y) - f(x',y') \le D\)。按照上面的方法建图即可。

2. P6054 [RC-02] 开门大吉

设第 \(i\) 位选手选第 \(j\) 套题的期望奖励为 \(g_{i,j}\)，则 \(g_{i,j} = \sum\limits_{k=1}^p c_k \times \prod\limits_{l=1}^k f_{i,j,l}\)。

但是这题的约束是 \(x_{u_i} \ge x_{v_i} + w_i\) 了，怎么办呢？

仍然采用类似的思想建图，连 \(n\) 条链，对于每个约束，每个点向他能选的最近点连 \(\infty\) 边，即 \(p_{v_i,j} \to p_{u_i,j+w_i}\)。注意若这样连则 \(j + w_i > m\) 的点没有限制，于是对于这些点还需连 \(p_{v_i,j} \to p_{u_i,m+1}\)，表示它们不能被选。