首页 > 编程学习 > P2403 [SDOI2010]所驼门王的宝藏 题解(Tarjan+SPFA)

事实证明,卡常是可以过的。

这题无需排序,无需用哈希代替 map,只要卡常到位就能过。

首先暴力建图是不可取的,很容易卡。所以我们要考虑优化。

第三种门显然只能暴力建边,至于前两种的话,由于那些同类型且在同行(如果是第二种门的话就是同列)的门互相可以到达,考虑把他们建成一个环,再让其中的一个点向能抵达的其余点连有向边,这样的效果就与暴力连边相同了(因为其他传送门可以走到这点,再走向剩下的点,建成的图就像一个铁环下挂了很多钥匙)。这样图就建完了。

接下来我们利用 tarjan 缩点,把图变成一个 DAG,并建一个超级源向所有缩好的点连边(到达结点是由几个点缩成的,边权就是几),成为连通图,然后用 SPFA 从超级源开始跑一次最长路就好了。

不过这样会 MLE,只能得 60 分。

考虑卡常!!!!!!

  1. 把 i,j,k1,k2 等搞成全局变量(当然,tarjan 里的不行),节省空间。

  2. 重边没影响,增加的边的空间还是 mp1 的空间大,把 mp1 删掉。

  3. 能开 short 的开 short。

好,现在有 70 分了。

第四条优化来了,那就是 vih 与 vil 数组不需要,我们建一个环需要的信息只是它的头和尾(增加一个与尾连边,全部弄完后再把尾向头连边即可)。

于是······AC了。

现在回头再看,其实 一,三条优化不重要,重要的是二,四两条,有这两条我们就可以 AC 了。

Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000