SPFA跑费用流的复杂度是多少?

P2410 [SDOI2009] 最优图像

@[Gang_Leader](/space/show?uid=119261) 应该是$n^5$级别的吧……?
by chen_zhe @ 2019-02-01 17:36:05


@[chen_zhe](/space/show?uid=8457) 不会吧,[费用流模板](https://www.luogu.org/problemnew/show/P3381)$n$都有$5000$
by 7KByte @ 2019-02-01 17:37:50


这道题最大数据节点200个,连边20000条,然后被卡掉了$QAQ$
by 7KByte @ 2019-02-01 17:39:20


@[Gang_Leader](/space/show?uid=119261) 这是因为一般跑不满的缘故……
by chen_zhe @ 2019-02-01 17:42:42


如何优化?
by 7KByte @ 2019-02-01 17:50:12


![](https://cdn.luogu.com.cn/upload/pic/50742.png) 只剩两个点了……
by 7KByte @ 2019-02-01 17:56:51


|