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

by Park @ 2018-05-18 22:00:09

补充，虚拟点优化似乎也符合该题范围。

by caddy @ 2018-05-18 22:06:58

拓扑排序需要优化

根据 @mangoyang的题解

可以通过构建虚拟点来减少边数

将一个车经过的站连向虚拟点，

再将虚拟点连向未经过的车站

by newbie314159 @ 2018-05-18 22:07:03

普及组考线段树优化连边

QAQ

by caddy @ 2018-05-18 22:08:34

建议加强数据

@chen_zhe

by LJC00118 @ 2018-05-18 22:21:38

@caddy 普及组原题一般不予加强数据

by qqvq @ 2018-05-19 07:20:40

您怕是想多了吧，完全图才n^2条边，跑不满n^3的

by Rorshach @ 2018-05-19 08:36:51

最多确实要n^{3}条边

但我当时写的时候也没想那么多啊 毕竟这题考的是建模吧 而不是什么优化建边

线段树优化建边可以看一下cf786B 楼上题解提到的虚点方法确实很巧妙

@Ycrpro 这道题有重边的

by Rorshach @ 2018-05-19 08:38:58

刚说错了 开个矩阵判一下有无重边

但是加边复杂度为n^{3}无误

by qqvq @ 2018-05-19 09:17:16

@Rorshach 有重边可以不加，最多就是n^2级别条边，要是说空循环最高1e9次，我没话说。。。

by caddy @ 2018-05-19 16:35:40

如果不开 O2优化

即使是三层空循环也会超时。