最小割的代价建模四题
我们的目标都是最大化净收益,净收益=收益-代价
我们认为点集构成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
2021年11月25日 19:27
Mobikwik is a renowned payment App in India that is widely used to do mobile recharge, bill payment, DTH recharge, etc. There is an option in Mobikwik which provides its user with an option to save Remove Saved Card from Mobikwik the details of their bank cards. Here, a user can save the details of the card which he/she uses frequently while making their transactions through Mobikwik.
2023年3月02日 20:33
It’s a great platform regarding to one of our main problems! First I saw about them on the internet, and after linking to them I was really comfortable! Recommended to all! <a href="https://cdnguide.com/wordpress-cdn/">WordPress CDN</a>
2023年5月22日 19:25
The Meghalaya Board of School Education (MBOSE) will provide SSLC model papers with previous exam solved question banks, subject experts' recommended study material, as well as bit questions for Guessing the Important to Short Answer Questions, Very Short Answer Questions, and Objective Type Questions to modelpapers2019.com all Medium Collages Unit Tests, Quarterly, Half Yearly, and Annual Final Public Examination Tests in March 2023.The Meghalaya Board of School Education, Tura, will provide subject-specific study resources to all class 10th students, as well as an important question bank and answer answers. Furthermore, MBOSE subject specialists produced recommendations and supplied subject-specific study materials for the MBOSE tests 2023, as well as sample question papers and solved question patterns.