最小割的代价建模四题 - Hoblovski's Blog - 想拿Ag的蒟蒻.已经Ag滚出.
使用Dijkstra优化费用流
我的对拍代码库

最小割的代价建模四题

Hoblovski posted @ 2014年7月16日 14:31 in Notes with tags 最小割 笔记 网络流 , 768 阅读
我们的目标都是最大化净收益,净收益=收益-代价
我们认为点集构成G.V,(u,v)这样的二元组集合构成了一个图G.E,于是使用图模型来叙述
以下提到(u,v)的时候省略(u,v) in G.E的前提,
u,v一个选一个不选记为 Diff(u,v) 都选或都不选记为 Same(u,v)
 
1.POJ3469
N个点,可以选或者不选,点u选有代价Au,不选代价Bu
Diff(u,v)则代价w(u,v),(u,v)(v,u)算1次
 
基本思想 把最后得到割删去后的S,T集赋予意义.
本题中认为属于S选属于T不选,那么显然建图
(S,u,Bu),(u,T,Au),(u,v,w(u,v))之后Ans=isap
 
2.BZOJ1976
二分图,N个点可以选或者不选,选或者不选没有代价.
有些点已经确定,Diff(u,v)则收益1,(u,v)(v,u)算1次
 
基本思想 补集转换,最大化收益等价于最小化代价
先黑白染色,得到强制所有黑点选,白点不选(无视确定的)的初始收益Low.
然后强制选或不选的代价为1,已确定选的不选代价oo,确定不选的选的代价oo
相邻点选一样的代价为1,S,T意义{属于S::黑点?不选:选;属于T::白点?不选:选}
所以
选的代价1
不选的代价1
Diff(u,v)代价1
 
3.BZOJ2037
一般图,N个点可以选或者不选,点u选代价Au不选无代价
u选了v选了收益w(u,v),u选了v不选代价w(u,v),(u,v)(v,u)都算2次
保证w(u,v)=w(v,u)
 
基本思想 补集转化,收益转代价
计算初始收益Low=Σw(u,v),选u代价Au
不选u则u不能和任何v产生w(u,v)的收益所以代价Σw(u,v)
Diff(u,v)代价2w(u,v),我们需要消去其中选的那个的w并且再减去代价
S,T意义{属于S::选;属于T::不选}
Au的贡献显然能正确计算,考虑w(u,v)的贡献
1.u,v都选 显然
2.u,v都不选 显然
3.u选v不选 显然
所以
选的代价Au
不选的代价Σw(u,v)
Diff(u,v)代价2w(u,v)
 
4.BZOJ2127
二分图,点可以选或者不选,选了的话有收益Au,不选的话有收益Bu
(u,v)in G.E,u,v都选了则收益w1(u,v),(u,v)(v,u)记一次
(u,v)in G.E,u,v都不选则收益w2(u,v),(u,v)(v,u)记一次
 
基本思想 补集转化,收益转代价
计算初始收益Low=Σw1(u,v)+Σw2(u,v)+ΣAu+ΣBu,其中(u,v)(v,u)算1次
我们不妨认为w1(u,v)/2=w1'(u,v),w2(u,v)/2=w2'(u,v),之后(u,v)(v,u)记两次.
选u的代价为Bu+Σw2'(u,v),不选的代价为Au+Σw1'(u,v)
Au,Bu贡献显然正确计算,考虑w1(u,v),w2(u,v)
1.u,v都选,Low中计算了w1(u,v)+w2(u,v),代价减去了2w2'(u,v)最终贡献w1(u,v)
2.u,v都不选,类似上述可证.
3.u选v不选,Low中计算了w1(u,v)+w2(u,v),代价减去了w2'(u,v)以及w1'(u,v),我们还需要减去w2'(u,v)+w1'(u,v)
所以
选的代价 Bu+Σw2(u,v)/2
不选的代价为Au+Σw1(u,v)/2
Diff(u,v)代价w1(u,v)/2+w2(u,v)/2

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter