大部分拓扑排序题解是否存在问题

Park @ 2018-05-18 21:58:03

by BJpers2 @ 2018-06-07 20:56:11

楼主说的很对，建图是的确需要N^3的复杂度。但是实际请况是每次读入一条线路，最多覆盖长为N的区间，需建的边数为s*(N-s),至多为N^2/4条，实测最大的一个点只有不到20,000,000条边（算重加的）。

by BJpers2 @ 2018-06-07 20:57:46

多打了一个0,只有两千万

by BJpers2 @ 2018-06-07 20:58:30

啊，脑子抽了，我啥也没说

by retired_treasure @ 2018-06-17 13:06:21

不会。最坏复杂度为

(n/2)*(n/2)*m=n*n*m/4=1000*1000*250=5000*5000*10.

常数优化后能过 。

by retired_treasure @ 2018-06-17 13:08:04

@Park 毕竟1000³也大不到哪去，只比5000²大40倍，常数优化可过（那些说空循环过不了的，break和continue你们考虑没）

by Park @ 2018-06-17 15:25:03

@treasure n<=1000,O(n^3)的复杂度如何才能常数优化到1s以内,求教