补充，虚拟点优化似乎也符合该题范围。
by Park @ 2018-05-18 22:00:09
# **拓扑排序需要优化**
根据 @mangoyang的题解
可以通过**构建虚拟点**来减少边数
将一个车经过的站连向虚拟点，
再将虚拟点连向未经过的车站
$O(n^2)$解决
by caddy @ 2018-05-18 22:06:58
普及组考线段树优化连边
QAQ
by newbie314159 @ 2018-05-18 22:07:03
建议加强数据
@[chen_zhe](/space/show?uid=8457)
by caddy @ 2018-05-18 22:08:34
@[caddy](/space/show?uid=36310) 普及组原题一般不予加强数据
by LJC00118 @ 2018-05-18 22:21:38
您怕是想多了吧，完全图才n^2条边，跑不满n^3的
by qqvq @ 2018-05-19 07:20:40
最多确实要$n^{3}$条边
但我当时写的时候也没想那么多啊 毕竟这题考的是建模吧 而不是什么优化建边
线段树优化建边可以看一下cf786B 楼上题解提到的虚点方法确实很巧妙
@[Ycrpro](/space/show?uid=29089) 这道题有重边的
by Rorshach @ 2018-05-19 08:36:51
刚说错了 开个矩阵判一下有无重边
但是加边复杂度为$n^{3}$无误
by Rorshach @ 2018-05-19 08:38:58
@[Rorshach](/space/show?uid=59303) 有重边可以不加，最多就是n^2级别条边，要是说空循环最高1e9次，我没话说。。。
by qqvq @ 2018-05-19 09:17:16
如果不开
O2优化
即使是三层空循环也会超时。
by caddy @ 2018-05-19 16:35:40