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 4536 >> 这样迭代对不对?
save_code @ 2018-07-01 05:23:51
[ Quote ] [ Edit ] [ Delete ] 1#
先把所有边的容量 都设成1, 然后跑网络流, 如果 某一条关于n的边 没有满流 然后 按照优先级迭代, 枚举 关于m的边 把一条边容量加2,然后 继续跑网络流,如果 这两个容量都满了继续加2 迭代,一直迭代到 不能满流跳出,如果 关于N的边慢了,这就是答案,如果没满, 然后按照 从小到大的顺序枚举M的边,每次 容量加1,继续跑网络流 ,直到N满了位置。

这个算法 应该没错吧, 然后复杂度 好像比较高,但至少是多项式的。。。
save_code @ 2018-07-01 05:28:33
[ Quote ] [ Edit ] [ Delete ] 2#
够暴力了啊、。、。
save_code @ 2018-07-01 14:04:22
[ Quote ] [ Edit ] [ Delete ] 3#
能多给几组样例吗、???
save_code @ 2018-07-03 10:29:05
[ Quote ] [ Edit ] [ Delete ] 4#
这道题 好像可以回流 一对增广路径,然后 新产生 2对 新的增广路径 实现起来好麻烦。。。
save_code @ 2018-07-03 10:41:38
[ Quote ] [ Edit ] [ Delete ] 5#
减2+4 最麻烦啊,也就是 有两条边只能增广1次,然后 某一条边 可以增广2次,然后 可以把增广两次的边撤掉,给这两个一次的边,然后就生成了2条两次的边。。。
save_code @ 2018-07-03 10:42:28
[ Quote ] [ Edit ] [ Delete ] 6#
不知道 所有情况都考虑完了没有,还有没有其他情况
save_code @ 2018-07-03 16:54:14
[ Quote ] [ Edit ] [ Delete ] 7#
YES AC了。。。哈哈哈
[Top] [Previous Page] [Next Page]

HOME Back