因为原图是棵树
by scallop @ 2018-07-09 20:32:34
@[scallop](/space/show?uid=25739) 可以具体说明一下原理吗
（复杂度证明之类的？？？）
by niiick @ 2018-07-09 20:35:28
@[niiick](/space/show?uid=60885) emm...
by かなで @ 2018-07-09 20:48:41
@[niiick](/space/show?uid=60885) 最多n条増广路，每条长度为n，最坏复杂度O(n^2)
by かなで @ 2018-07-09 20:49:39
所以是数据水
by かなで @ 2018-07-09 20:50:02
@[niiick](/space/show?uid=60885)
卡掉dinic需要一些奇奇怪怪的图，一般都是带很多大环的（闷声成大环）。
参考[如何使最大流的 Dinic 算法达到理论上的最坏时间复杂度？](https://www.zhihu.com/question/266149721)
非形式化地解释，如@[scallop](/space/show?uid=25739) 所说的，原图是一棵树，因此残存网络不会出现由反向边构成的增广路径。（只会正着走过去，不会倒着走回来）因此复杂度小得可怕。
形式化的严谨证明……我太菜了，对我来说有点难度，交给别的大佬吧。
by silverxz @ 2018-07-09 21:15:23
@[かなで](/space/show?uid=100018) 你这个界是不是太松了？一共n个结点，没法保证既有n条增广路，每条增光路长度还都是n。
by silverxz @ 2018-07-09 21:19:05
@[silverxz](/space/show?uid=48658) 灰常感谢巨佬的回答
by niiick @ 2018-07-09 21:20:30
@[silverxz](/space/show?uid=48658) 一半链一半菊花图卡成n方
by かなで @ 2018-07-09 21:58:06
@[かなで](/space/show?uid=100018) 啊……是的大佬你是对的。我今天考试的时候想到了……用一棵斜歪的树可以卡成$n^2$……然而菊花图是什么？可以描述一下么？
by silverxz @ 2018-07-10 17:23:11