除旧迎新限时题-虎

坐牢了兄弟们

只能说刚结束我就想到了正解，样例过了就等于过了

炸内存可太坐牢了

首先是一个猜想，当前仅当断开了所有最长路径都经过的边才会对答案造成影响。

这个猜想应该是对的，因为如果假设当前断开的这条边不是所有最长路径都会经过，那么必然有其他的最长路径是能走完全程的，那么答案依然是最长距离。

那么最后的思路就是找到最长的距离，我们标记所有最长路径都经过的边集为MaxEdges，最长路径会经过的边为LongEdges，显然MaxEdges是LongEdges的一个子集（也有可能相等）。那么我们在dfs遍历的时候只走LongEdges，遇到MaxEdges时，模拟断开这条边的情况。

首先构造一组样例

可以得到原图长这样

我们翻转以后进行拓扑排序计算dis，然后对应的dis值放回原图就能够得到每个点最远能走多远

然后我们就能够确定LongEdges是哪些边了，很明显从dis值最大的点开始遍历，设x为当前节点，i为x的后继节点，当dis[x] == dis[i] + 1时，x->i可以被看做属于LongEdges。

下一步我们要找到哪些边是所有最长路径都会经过的边，我们先确定一个MaxDis表示dis数组中的最大值，MaxFlow表示dis数组中有多少个元素等于MaxDis ，设置一个flow数组，先初始化，若dis[x] == MaxDis，则将flow[x]标记为1。

下图中绿色的边是LongEdges，红色是MaxEdges。

被画上圆圈的是属于LongEdges的边，每个点的flow值会传递给属于LongEdges集合的后继节点，比如flow[2] = flow[1] / 1 + flow[3] / 1。值得注意的是flow[4] = flow[5] / 2，因为节点5有两条出边，且都是属于LongEdges，因此flow值要对半分，而2->4这条边不属于LongEdges，flow[2]的值将不会传递给flow[4]。

那么很显然当flow[x] == flow[y] == MaxFlow时，x->y这条边将会是所有最长路径都必须经过的边。

请注意，因为LongEdges是MaxEdges的子集，所以同时需要满足dis[x] == dis[y] + 1，当你把此条件作为向下递归的约束时可以省去，也就是按照LongEdges边集递归。

我们此时可以枚举断开这条边的后果，如果断开这条边后没有其他的边了，那么结果就是answer = min(answer,step)。step为你递归到当前节点的步长。如果还存在其他边，那么毫无疑问要取所有后继节点中dis值最大的一个节点，answer = min(answer,max(dis[i]) + step + 1)，i是当前节点其他的后继节点。

那么回到样例，一开始我们可以初始化ans为MaxDis，也就是4。

我们可以发现只能断开2->5这条边，因为dis[2] == dis[5] + 1 && flow[2] == flow[5] == MaxFlow == 2

断开该边后，2仍然有后继节点4和6，那么max(dis[4],dis[6]) + step + 1，走到节点2的step为1，dis[4] = dis[6] = 1，所以最终结果是3。

补充一点，为了防止超时，应当为已经遍历过的点打上标记

好猜！