ZigZagK

Never give up fighting!

最小割模型

对《最小割模型在信息学竞赛中的应用》的一些口胡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{align}
|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{align}
\]
如果我们把 \(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{align}
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{align}\\
\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

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注