P3705 [SDOI2017] 新生舞会
Zhl2010
·
·
个人记录
P3705 [SDOI2017] 新生舞会。
题目要求最大化：
\frac {a'_1+a'_2+...+a'_n}{b'_1+b'_2+...+b'_n}
我们很容易发现我们需要让一个分数尽可能大，所以很容易想到 01 分数规划。这是 01 分数规划的常见形式：
\displaystyle\frac{\sum\limits_{i=1}^na_i\times w_i}{\sum\limits_{i=1}^nb_i\times w_i}
（其实特殊形式也算给了一点提示，因为 01 分数规划有一个变式就是下面全是 1，那个特殊性质也是 b 全是 1）。
然后 01 分数规划的整体思路是移项，然后二分求解：
\begin{align*}
\frac {a'_1+a'_2+...+a'_n}{b'_1+b'_2+...+b'_n}&\ge \operatorname{mid}\\
a_1+a_2+\cdots + &\ge \operatorname{mid}\cdot(b_1+b_2+\cdots b_n)\\
(a_1-\operatorname{mid}\cdot b_1)+(a_2-\operatorname{mid}\cdot b_2)\cdots(a_n-\operatorname{mid}\cdot b_n)&\ge 0
\end{align*}
但是这个东西是有限制的，每一个权值有对应的男生和女生。
于是我们就可以有新的权值 v，所以需要二分图最大权匹配来求出最优的匹配看看最后的权值是否大于 0。
然后考场上的我还剩 1h，想想网络流感觉复杂了，于是认为有一个我不知道（或者是学过忘了）的算法来求这个东西，然后代码写了一半，错了。甚至认为自己完全想偏了？
最后...模拟退火，原本期望应该是 70，实际 40（甚至评测高峰只有 30？）。
其实二分图最大权匹配可以用 KM（我不会），但是一般我们就是用费用流（听到这道题费用流就完了，我...），这道题我们可以从源点向男生连边，然后男生向女生连边，费用为 (a_{i,j}-\operatorname{mid}\cdot b_{i,j})，最后女生向汇点连边，流量都为 1。
建议费用流就用 EK 了，普通最大流再用 dinic。~难点：是否还会写 EK 的最小费用最大流。~
这道题如果想到了还是很简单的...