对于『跑 \(n\) 遍』性质的利用。
https://www.luogu.com.cn/problem/P10805
容易注意到可以二分答案;但似乎没办法找到一种很好的方法在 \(O(n)\) 内完成一次 check。
化用一下网络流中流量的概念;例如下面这个图,假如先从 \(0\) 开始跑,发现没办法很好地确定 \(8\to 2\) 这条边的流量(原因:没办法确定 \(8\) 和 \(2\) 的搜索顺序)。
这个时候想到;如果是 \(2\) 先被搜到,自然很好;但如果是 \(8\) 先被搜到,可以忽略这条由它出发、且未确定的边,先由现在认为的流出量确定流入量。等搜到 \(2\) 的时候,再更新一下 \(8\to 2\) 的流量。这样 \(8\) 的流入量就是错的;容易想到再搜一次来更新。
类比一下 SPFA,可以认为跑 \(n\) 遍就已经达到能更新的最终状态。此时 check 一下是否每个点都合法。