ZigZagK的博客
最小割模型
2018年3月8日 20:14
图论
查看标签

对《最小割模型在信息学竞赛中的应用》的一些口胡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

版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!