@[yummy](/user/101694) Dinic的一次DFS最多$ O(nm) $，然后又只会构造$ n $次层次图，总复杂度就是$ O(n^2m) $qwq
前提是要加上一堆优化，不然就是$ O(nm^2) $qwq
by Prean @ 2020-07-04 09:08:14
@[limaopipi2022](/user/160839) 啊我的意思只怎么保证这题能过啊，你看这题 $N\leq 10^4$， $N^2M$大概末尾有12个零
by yummy @ 2020-07-04 09:22:21
放心，原则上不卡 $Dinic$
by wlzhouzhuan @ 2020-07-04 09:22:46
@[wlzhouzhuan](/user/112381) 说好“一道题需要保证所有在该数据范围内的数据都能让标程通过”的呢？
我个人觉得如果无法证明复杂度是需要找管理处理一下的
by yummy @ 2020-07-04 09:27:12
@[yummy](/user/101694) 一般情况下网络流复杂度是不会满的，而且法律规定不能卡Dinic和ISAP，但是可以卡EK
by Prean @ 2020-07-04 09:28:04
@[limaopipi2022](/user/160839) 哪里的法律，我想看
一般情况不满，我是不是还能放心用SPFA，SPFA一般情况也不满
暴力匹配字符串绝大多数情况也是几乎线性的呢
by yummy @ 2020-07-04 09:28:59
@[yummy](/user/101694) 这题窝没看...反正就是二分图$O(Nsqrt(M))$复杂度吧
by 春待ち @ 2020-07-04 09:29:04
我想想...首先我可能还需要学习下如何证明二分图NsqrtM，然后才能证明这题的复杂度或者Hack it
by yummy @ 2020-07-04 09:32:02
@[limaopipi2022](/user/160839) 法律在哪里啊qaq
by yummy @ 2020-07-04 09:34:16
@[春待ち](/user/297420) 二分图是msqrt(n)不是nsqrt(m)
by 142857cs @ 2020-07-04 09:35:05