最小割小结

《浅析一类最小割问题(pty)》
这算是个解决最小割问题比较统一的方法吧 感觉是很厉害O.O
这个就是把最小割模型都转化成二元关系:(x,y)
x,y都取 代价为v1
x,y都不取 代价为v2
x取y不取 代价为v3
x不取y取 代价为v4
对于这个图233

a + b = v1
c + d = v2
a + d + f = v3
b + c + e = v4

令K = v3 + v4 – v1 – v2

如果 K < 0 那么关系图要是二分图就能做 把一侧的定义相反即可(这个的题目很少 不详写= = 首先要保证边权是非负的 K >= 0 e和f一定是非负的
可以看到每个等式中都出现了a、c中的一个 b、d中的一个
如果a、c中有边权是负的 可以把它们同时加上一个数 最后再扣掉
b、d同理
还有最好保证他们都是整数
如果出现小数 可以把所有边权都*=分母的最小公倍数 最后再除掉 (这个最小公倍数一般是2什么的= =)
然后就可以直接建图了

对于一些一元关系 某个点取有多少获利 不取有多少获利什么的 最后直接建边即可
这里对每对二元和一元关系的建边是独立的 最后再把边权加起来作为边权(不加也可以) 而不是比如对于每个二元关系s->p的权值都是一样的

注意这里求的是最小割 是最小值 有的题目求的是最大获利
有两种转化方法
一是把权值取负 然后求最小获利
二是比如你取了某个点 说明你不能不取这个点 就失去了不取这个点能获得的获利 这样就变成了最小代价了 然后最后把权值和-最小代价就是最大收益
↑其实这两个方法好像是等价的 看你怎么理解罢了=-=

==========BZOJ 3438: 小M的作物===========
这题是一个多元关系 但是也可以转成一元的
对于每个作物 s到它的边表示这个作物选择A 到t的边表示选择b
对于每个组合 新建两个点
一个点表示这些点是否全部选了A 这个点选择是的收益是c1i 否的收益是0
另外一个表示这些点是否全部选了B 这个点选择是的收益是c2i 否的收益是0
s到第一个点的边表示 是全部取A 到第二个点的边表示 不是全部取B
第一个点到t的边表示 不是全部取A 第二个点到t的边代表 是全部取B
如果第一个点选择了全部取了A 但是组合里的某个作物选择了B 这样的代价就是inf 因为是不可行的= =
对于B同理
这样就把多元关系转成了二元关系 很多多元关系的题目都可以用这个思路
然后把这个方程列啊列 最后建出来的图是一个类似最大权闭合子图的东西O.O

==========BZOJ 2127: happiness===========
这个就是非常模板的题
说一点0 0
在很多情况下可以设e=f(比如这题)
但是也有的时候设两个变量比较方便(比如上面那题) 自己看着办吧233

==========BZOJ 3218: a + b Problem===========
这题是厉害啊 我决定为这题独立开一篇文章 以表(pian)敬(I)意(P)

发表评论