对《最小割模型在信息学竞赛中的应用》的一些口胡QAQ。

分数规划

(01)分数规划为下面一些问题作准备……基本上都是二分答案的套路。

分数规划+最小割：ZOJ2676

最大权闭合图

给出一张带点权的有向图，你可以选出一些点，如果这些点中任意一个点连接到的点均在选出的点中，则称这张图是闭合图，得到的价值是选出的点的点权之和，求最大权闭合图。

我们可以这样搞：如果 $x$ 的点权 $w_x>0$ ，就建 $(S,x,w_x)$ 的边，否则建 $(x,T,-w_x)$ 的边，然后这张图中的边 $(u,v)$ 就建 $(u,v,+\infty)$ 。则最后的答案是：

$$ (\sum_{w_x>0}w_x)-MinCut(S,T) $$

为什么啊……假设选出的点集是 $V_1(S\in V_1)​$ ，没选的点集是 $V_2(T\in V_2)​$ ，用 $V^-,V^+​$ 表示 $V​$ 集合中点权为负和点权为正的点。由于要求割，$V_1​$ 和 $V_2​$ 之间不能有任何边相连，所以：

$$ (\sum_{w_x>0}w_x)-MinCut(S,T)=(\sum_{x\in V_1^+}w_x)+(\sum_{x\in V_2^+}w_x)-[(\sum_{x\in V_2^+}w_x)-(\sum_{x\in V_1^-}w_x)]\\ ans=w(V_1)=(\sum_{x\in V_1^-}w_x)+(\sum_{x\in V_1^+}w_x) $$

上下相等啊，所以答案就是所有正权减去最小割。

最大权闭合图经典模型：BZOJ1497

最大权闭合图：BZOJ4873

最大密度子图

给出一张 $n$ 个点 $m$ 条边的无向图，你可以选出一些点 $V'$ ，定义一种方案的密度为：

$$ {|E'|\over |V'|},E'=\{(u,v)|u\in V',v\in V',(u,v)\in E\} $$

求最大密度子图。

明显是01分数规划，所以先二分答案 $mid$ ，那么就是验证 $|E'|-|V'|mid\ge 0$ 。一种比较直接的方法就是令每个点的点权为 $-g$ ，每条边的边权为 $1$ ，因为一条边被选说明两个点都被选了，所以转化为了最大权闭合图。

这样点数和边数都是 $n+m$ ，因为二分精度为 $1\over n^2$ 即二分次数为 $O(log_2{m-{1\over n}\over{1\over n^2}})=O(log_2n)$ ，所以时间复杂度为 $O(log_2n\cdot Mincut(n+m,n+m))$ 。可能会炸啊，所以接下来说一种更好的算法：

最大化 $|E'|-|V'|mid\Leftrightarrow$ 最小化 $|V'|mid-|E'|$ ，我们可以把 $|E'|$ 转化为 $|V'|$ 的导出子图删去连出去的边，写出表达式就变成了这样子( $\overline{V'}$ 表示 $V-V'$ ，$d_x$ 表示 $x$ 的度数，$c(V',\overline{V'})$ 表示连出去的边的数量)：

$$ \begin{aligned} |V'|mid-|E'| &= |V'|mid-{\sum_{x\in V'}d_x-c(V,\overline{V'})\over2}\\ &={1\over 2}[(\sum_{u\in V'}2mid-d_u)-c(V,\overline{V'})] \end{aligned} $$

如果我们把 $2mid-d_u$ 当做 $u$ 的点权，那么我们可以这么建图：

$s\to u:0|(u,v):1|u\to t:2mid-d_u$

感性理解：切断 $(u,v)$ 或者选择 $u$ 都需要花费，那么最小花费就是最小割。

然后求出最小割就是答案了？？？这图怎么这么奇怪啊？实际上因为 $2mid-d_u$ 会爆负，所以我们给辅助边加上 $U$ 防止爆负（ $U$ 取 $m$ 即可），然后再求最小割。

可是加了 $m$ 之后最小割就不表示上面那个验证式子了。我们推一下：

$$ \begin{aligned} c[S,T]&=\sum_{ u\in \overline{V'} }c_{ s,u }+\sum_{ u\in V' }c_{ u,t }+\sum_{ u\in V',v\in \overline{ V' },(u,v)\in E}c_{ u,v }\\ &=U|\overline{ V' }|+\sum_{u\in V'}(U+2mid-d_u+\sum_{v\in \overline{V'},(u,v)\in E}1)\\ &=U|V|+\sum_{u\in V'}(2mid-d_u+d_u-\sum_{v\in V',(u,v)\in E}1)\\ &=U|V|+\sum_{u\in V'}(2mid-\sum_{v\in V',(u,v)\in E}1)\\ &=U|V|+2mid|V'|-2|E'|\\ &=Un-2(|E'|-mid|V'|) \end{aligned}\\ \Updownarrow\\ |E'|-mid|V'|={Un-c[S,T]\over 2} $$

所以只要求出最小割 $c[S,T]$ ，然后验证 $Un-c[S,T]\ge 0$ 就行了。但是要注意一个细节，这么建图我们可以发现能够从 $s$ 遍历到的点就是被选的点，而最大密度子图是不允许不选( $c[S,T]=Un$ )的，所以验证条件应该为 $Un-c[S,T]>0$ 。

这样点数为 $O(n)$ ，边数为 $O(n+m)=O(m)$ ，达到了下界。

最大密度子图：POJ3155

最大密度子图(边权&点权)

还是套用上述模型，令点权为 $p_u$ 边权为 $w_e$ ，那么二分枚举 $mid$ 之后，点权变成了 $2mid-2p_u-d_u$ ( $d_u$ 定义为与 $u$ 相连的边的权值和)，边权从 $1$ 变成了 $w_x$ ，所以这么建图：

$s\to u:0|(u,v)=w_e|(u\to t):2mid-2p_u-d_u$

(ps：$2mid-2p_u-d_u$ 是新点权，有些题目可能直接就推出新点权了，反正分析对就行了QAQ)

还是可以得到：验证函数 $={Un-c[S,T]\over 2}$ ，所以和之前一样判断就行了。

但是二分范围和精度还有 $U$ 的范围都需要变化，根据题意分析即可。

带边权点权的最大密度子图：计蒜客15549