LuoguGym分析考虑线性规划。设 $x_i$ 为第 $i$ 小时是否吃饭，可以列出线性规划用 NOI2008 志愿者招募 一题的方法建图求最大费用最大流即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==============...
标准型与松弛型线性规划是这样一类问题：有一些非负变量 $x_1,x_2,\cdots,x_n$。这些变量满足一些线性不等式。最小化/最大化目标函数 $z=\sum_{i=1}^nc_ix_i$。线性规划问题的标准型为然后可以证明，这两个问题的最优解是相等的。感性理解可以看 hyj 的文章。单纯形我不会，待填
Luogu分析这是一个线性规划做法。下面举的栗子为样例。设 $X_i$ 为第 $i$ 类志愿者的招募数，$P_i$ 为第 $i$ 天招募志愿者的数量，那么可以列出一些不等式注意到每个变量恰出现 $2$ 次且系数一正一负。我们可以把每个等式看做一个点，正数代表流出，负数代表流入，那么等式相当于流量平衡。因此我们得到了这样的建图方法：如果 $P_i-P_{i-1}>0$，从源点向 $i$ ...