loj6001

题目链接

loj6001

题解

网络流24题之二,最大权闭合图,之前有写过.

建模就是需要增加一个源点\(s\)和汇点\(t\),将原图中的所有的有向图的边\(u,v\)替换成容量为\(c(u,v)=\infty\)的有向边\(u,v\).

连接源点\(s\)到原图的每一个正权点\(v\)的有向边,容量记为\(w\),对于题中说的负权点\(v\),需要连接至汇点.容量记为\(-w\).

最后最大权闭合图的权值=正权值总和-最小割容量

证明?戳我


By:Wahacer

2018.3.3

12:49

发表评论

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