关于网络流的问题
  • 板块学术版
  • 楼主astwe
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/10/11 11:13
  • 上次更新2023/11/2 14:31:39
查看原帖
关于网络流的问题
531136
astwe楼主2023/10/11 11:13

dinic的复杂度为O(n2m)O(n^2m)为啥那么多题都能解决啊,比如P1646点数为n2n^2,边数也为n2n^2,复杂度应为O((n2)2∗n2)O((n^2)^2*n^2),应为O(n6)O(n^6)可是这肯定不能过把。还有这题P1361也是一样的。

另外费用流复杂度oiwiki上写着是O(nmf)O(nmf),可是费用流板子的 f 很大啊,另外那个SSP算法用EK和dinic实现是一样复杂度的吗?

2023/10/11 11:13
加载中...