F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 2235 >> Sol
lavendir @ 2018-07-14 10:40:56
[ Quote ] [ Edit ] [ Delete ] 1#
对于所有正权点i,从S连到i,流量为i的权值。
对于所有负权点j,从j连到T.流量为-j的权值。
对于原图中的所有边保留,流量为无穷大
设C为此图最小割,那么所有正权点的权和-c就是最优解
[Top] [Previous Page] [Next Page]

HOME Back