written on 2022-08-09
题目不难，但是需要总结一下。
题意很明确，就不过多阐述了。读完题目后，很明显可以建反图，然后就会有两种方法。
第一种方法是直接拓扑排序找环，这种方式是可行的，但是由于存在自环、找到环后还要记录是否由终点可达许多繁琐的信息，实际操作过程中的细节会十分琐碎，因而导致最后可能会写爆掉。实际比赛的时候也确实是这样/kk
这里采用第二种方法，即先用 \(\tt{tarjan}\) 找出强连通然后缩点，这样的话，在跑拓扑排序时，可以规避掉环的情况，然后用类似 \(\tt{dp}\) 的形式累加（\(dp_y\leftarrow dp_y+dp_x\)）。注意跑到大小大于 \(2\) 的强连通或是自环时将 \(dp\) 数组更新为 \(36501\)。然后如果累加时 \(dp\) 数组已经大于 \(36501\) 就对其取 \(\min\)。这种方法的好处就是思路更加清晰，不容易写爆。
总结：以后在能采用强连通分量缩点的情况下尽量不用拓扑排序找环，否则可能会因为一些离奇的细节爆掉。
标签：连通,拓扑,POI2006,62,tt,找环,排序,Pro,dp From： https://www.cnblogs.com/Freshair-qprt/p/16585600.html