博主比较菜QwQ,一直学不会最小割,全靠背板子背模型来做(chao)题(jie)。
省选和CTSC打完(beng)了,于是对以前学的网络流的最小割算法进行一些简单的总结。最小割
本文讨论的最小割都是源汇最小割,关于全局最小割请自行学习。源汇最小割,简单来讲就是切去一些边使得源汇不连通,并使得删去的边权权值最小。
常用的方法是跑一遍最大流,关于为什么最大流等于最小割会在随后给出(简单解释一下,最小割是最大流的对偶问题,根据强对偶定理,两个的最优解相同)。集合划分
因为源汇最小割即就是将源汇划分到不同的集合,那么最简单的应用大概就是最小代价划分集合了。本文用\(S\)表示网络流图中的源点,用\(T\)表示网络流图中的汇点。
我们尝试定义一下这个限制:有\(n\)个变量\(x_i\),取值为\(\{0,1\}\),要最小化函数\(z=\sum_{i=1}^n{w_ix_i}\),那么就可以很形象地用最小割模型描述这个约束:对于一个点\(i\),\(x_i\)为\(1\)表示\(i\)和\(S\)同属一个集合,即割去\(i\)与\(T\)之间的边,代价是\(w_i\)。
但在实际上如果令一个点与\(T\)同属一个集合,同样会删去一些边,产生权值。为了描述这些情况,我们构造一种使得当\(x_i=0\)时产生代价的限制。这个可以很显然地构造出:\((1-x_i)w_i\)
那么对于这一类划分集合问题,我们可以建出最小割模型:
每一个点能且仅能被划分到两个集合中的一个集合。其中划分到第一个集合代价为\(a_i\),划分到第二个集合代价为\(b_i\),求最小划分代价。
可以很方便地列出这类问题的约束函数:
\[ z=\sum_{i=1}^n{a_ix_i+b_i(1-x_i)} \] 然后很轻松地按定义建图:对于一点\(i\):- 从\(S\)向\(i\)连\(b_i\)的边
- 从\(i\)向\(T\)连\(a_i\)的边
此时最小割就是最小代价。
然而即使是连noip普及组都拿不上奖的博主都能发现:这难道不是直接贪心。。。
但最小割不仅能够解决简单的集合划分,还能解决带某些约束的集合划分。
比如在原题上加一些条件:
给定一些约束\(i,j\),当\(i,j\)被划分到不同集合,那么会产生额外的代价\(c_{i,j}\)
就无法直接贪心了= =
我们先列出约束函数:\(z=\sum_{i,j}{c_{i,j}x_i(1-x_j)+c_{i,j}x_j(1-x_i)}\)
拆出来考虑\(c_{i,j}max(0,x_i-x_j)\),也能感性的构造出一种构图方式:当且仅当\(i\)属于\(S\)且\(j\)属于\(T\)时产生权值,此时从\(i\)向\(j\)连权值为\(c_{i,j}\)的边。因为当\(i\)属于\(S\)且\(j\)属于\(T\)时必须割掉这条边才能完成集合划分。
于是这一类问题就被我们很好的解决了。
此时我们再考虑一类问题:
求集合划分的最大代价
思路很显然,对答案贡献改为负权,最后对答案取反即可。但因为流量不能为负,不符合最小割模型的约定,所以这里要做一些改动。当\(w_i<0\)时:
\[ w_ix_i=(-w_i)(-x_i)=w_i+(-w_i)(1-x_i) \]得到最小割之后加上常数项并取反就是我们想要的答案。
最大权闭合子图
简单来说就是一类依赖问题:
若\(i\)选则\(j\)必选,或是若\(i\)不选则\(j\)必不选。
我们可以尝试构造约束函数:\(z=\sum_{i,j}{\infty x_i(1-x_j)}\) 以及 \(z=\sum_{i,j}{\infty(1-x_i)x_j}\)
思路很显然,\(\infty\)的权值表示这里不应该产生贡献(否则非常大,除非没有其他选择)。
连边方法同理。当两个变量属于特定的不同的集合时才会产生贡献,那么就和划分集合部分的连边方式同理了。
其他的一些约束
我们发现我们可以通过一些特殊的方式来列出我们想要的约束。下面是一些简单的具体应用。
互不共存问题:
\(i\)和\(j\)不能同时存在
即\(z=\infty x_ix_j\)
构造变量\(y_i\),使得对于约束\(i,j\),\(x_i,y_j\)必须共存,\(y_i\)代价与\(1-x_i\)相同。这样只要\(x_i,y_i\)不共存,则就能保证正确性。而因为\(x_i,y_i\)连边是二分图,必然保证不共存。最终答案除以二即可
(这里利用了\(\infty\)一定不会产生贡献的性质,不能推广到一般权值)
当若干点同属某个集合时有额外贡献。求最大代价。
为了简单描述,认为若干点只有两个,是\(i,j\)。即求\(z=wx_ix_j=w+(-w)(1-x_ix_j)\)
令\(y=x_ix_j\),则有:
\[ z=w+(-w)y+\infty |y-x_i|+\infty |y-x_j| \]正常连边即可。绝对值即连双向边。
本文只是简单介绍了一些常见情况,仅用以抛砖引玉。这种通过列约束建图方法具有较强的普适性和易理解性,也可以进行一定的扩展。
例题以后再补。。。