01 分数规划

有 \(n\) 个 01变量 \(x_1\sim x_n\)，同时有 \(a_1\sim a_n,b_1\sim b_n\).

同时有约束条件：用集合 \(S\) 表示，这个 \(S\) 中每一个元素表示一个 \(x_1\sim x_n\) 的取法。（平时见到的题不咋有约束）

我们要给 \(x_1\sim x_n\) 赋值，使得 \(\dfrac{\sum x_ia_i}{\sum x_ib_i}\) 最大，还要满足 \(x_1\sim x_n\) 的取法 \(\in S\)。

先看看这个初始问题怎么解，再看拓展。

定义：

\(R(x)=\dfrac{\sum a_ix_i}{\sum b_ix_i}\)，\(R^*=\displaystyle\max_{x\in S}R(x)\)，目标是求得 \(R^*\)。

\(F_{\lambda}(x)=\sum a_ix_i-\lambda\sum b_ix_i\)。定义 \(F_{\lambda}^{*}=\displaystyle \max_{x\in S}F_{\lambda}(x)\)

重要定理：

\(R^*>\lambda \iff F_{\lambda}^*>0\)，\(R^*\ge\lambda \iff F_\lambda^*\ge0\)。

如果证明了这个定理，我们就可以得出：

（\(R^*\) 与 \(\lambda\)） 的大小关系，和 （\(F_\lambda^*\) 与 \(0\)） 的大小关系相同。

定理证明：

\(R^*>\lambda\iff \exists \,x\in s,R(x)>\lambda\iff \exists x\in S,\sum a_ix_i>\lambda\sum b_ix_i\iff \exists x\in S,\sum a_ix_i-\lambda\sum b_ix_i>0\iff \exists x,F_{\lambda}(x)>0\iff F_{\lambda}^*>0\)

把 \(>\) 改成 \(\ge\)，证明过程也还是正确的。证毕。

如此我们就可以二分，然后利用 \(F_\lambda^*\) 判断 \(R^*\) 是否可行。

注意：这里 \(F_\lambda(x),F_\lambda^*\) 的作用只是帮助我们判断 \(R^*\) 是否可行。具体我们要怎么求出 \(F_\lambda^*\)，就具体问题具体分析。

例题：Earthquake

每个边有两个属性 \(c_i,t_i\)。选出图中的一些边，构成生成树，使得 \(\dfrac{f-\sum c_ix_i}{\sum t_ix_i}\) 最大，\(x_i=0\) 表示此边没选，\(x_i=1\) 表示此边选了。其中 \(f\) 是给定的数。

解：

记 \(ans=\dfrac{f-\sum c_ix_i}{\sum t_ix_i}\)，\(f-\sum c_ix_i-ans\cdot\sum t_ix_i=0.\)

目标是使 \(ans\) 最大。

这里的 \(F_{\lambda}(x)=f-\sum c_ix_i-\lambda\cdot \sum t_ix_i\)。当我们二分一个 \(\lambda\) 判断是否可行，就是要判断 \(F_\lambda^*=\displaystyle\max_{x\in S}F_\lambda(x)\) 是否 \(>0\)，其中 \(S\) 是所有使得选出的边构成生成树的 \(x\) 的集合。

那么 \(F_{\lambda}(x)=f-\sum c_ix_i - \lambda\cdot \sum t_ix_i=f-\sum x_i\cdot (c_i-\lambda t_i).\)

要 \(F_\lambda(x)\) 最大，\(f\) 是常数，所以就是要 \(\sum x_i\cdot (c_i-\lambda t_i)\) 最小。

问题变成了：有一些边，可以选或者不选（\(x_i=0/1\)），每条边有一个属性 \(c_i-\lambda t_i\)，要求选一些构成生成树（\(x\in S\)），使得选出的这些边属性之和最小。

这不就是最小生成树吗？我们将每条边的权值赋值为 \(c_i-\lambda t_i\)，然后跑最小生成树得到最小总和 \(sum\)，再判断 \(f-sum\) 是否为正即可。

最小圈

老经典了。

\(ans=\dfrac{\sum w_ix_i}{\sum 1\cdot x_i}\) 最小。

\(F_\lambda(x)=\sum x_i\cdot(w_i-\lambda)\)，\(x\in S\)，这里 \(S\) 是所有构成环的边的选法集合。

我们要 \(ans\) 最小，也就是要 \(F_\lambda^*=\min F_\lambda(x)<0\)，也就是要选出若干条边构成环使得环的边权和小于 \(0\)。

这就是 SPFA 判负环。所以我们二分 \(\lambda\)，每条边的边权设置为 \(w_i-\lambda\) 然后判断是否有负环。若有，答案可以更小；否则，答案更大。

Signtseeing Cows

\(ans=\dfrac{\sum v_ix_i}{\sum e_ix_i}\) 最大。

\(F_\lambda(x)=\sum x_i\cdot (v_i-\lambda\cdot e_i)\)，\(x\in S\)，这里 \(S\) 是所有构成环的选边方案。

要 \(ans\) 最大，也就是 \(F_\lambda^*=\max F_\lambda(x)>0\)，也就是 \(\sum x_i(v_i-\lambda e_i)>0\)。

但是我们只整过负环的啊？大于 \(0\) 怎么弄？

很简单：\(\sum x_i(\lambda e_i-v_i)<0\)。

还有最后一问题：一条边的边权要设成 \(\lambda e_i-v_i\)，那么这个 \(v_i\) 是跟着哪个端点呢？

注意到原图是有向图（无向图当作两个相反边），我们让每条边的 \(v_i\) 都跟着出点或者都跟着入点即可。

Hiking

如果你发现用 \(\sum_{i=1}^nx_ia_i\) 难以表示出分子/分母，可以尝试直接用 \(\sum_{i=1}^{cnt} a_i\) 来表示。

例如此题，如果用 \(\sum_{i=1}^n\) 的方式，\(ans=\dfrac{?}{\sum_{i=1}^n x_ib_i}\)，发现分子不好表示。

所以我们转而用 \(ans=\dfrac{\sum_{i=1}^{cnt}\sqrt{|l-x_i+x_{i-1}|}}{\sum_{i=1}^{cnt}b_i}\) 表示。

\(F_\lambda(x)=\sum_{i=1}^{cnt}(\sqrt{|l-x_i+x_{i-1}|}-\lambda b_i)\)。要使其最大。

\(x\in S\)，\(S\) 是使得 \(x_{cnt}=x_n\) 的所有选法集合。

我们可以用 DP 来求 \(F_\lambda(x)\) 最大是多少。

\(dp[i]\) 表示前 \(i\) 个落脚地，最后一天在第 \(i\) 个落脚地休息的最大 \(\sum_{i=1}^{cnt}(\sqrt{|l-x_i+x_{i-1}|}-\lambda b_i)\) 是多少。\(O(n^2)\) 做 DP。

判断 \(dp[n]\) 的正负即可。

（DP 还原方案不再多说了）

新生舞会

构建01分数规划 “选物品” 的模型。

画一张 \(n\times n\) 的方格表，格子 \((i,j)\) 代表第 \(i\) 个男生与第 \(j\) 个女生配对。我们要从这些格子里面选一些，让这些格子的 \(\dfrac{\sum a_i}{\sum b_i}\) 最大。

\(x\in S\)，\(S\) 是选出一些格子且每行每列恰有 \(1\) 个格子选出的选法集合。

\(F_\lambda(x)=\sum x_i(a_i-\lambda b_i)\)，也就是说我们重新设每个格子的价值 \(c_i=a_i-\lambda b_i\)。我们要 \(ans\) 尽量大，所以就要 \(F_\lambda^*\) 尽量大。

如何二分判定：每个匹配的价值是 \(a_i-\lambda b_i\)，求二分图带权最大完美匹配。直接上费用流。