机房测试:Lesson5!(正反拓扑维护最长链)

题目:

 

 分析:

这道题。。。真的累。。。

抛开一切正图反图拓扑的想法。

二分一个mid。考虑怎么check。

枚举每一条边,如果fs[ u ] + ft[ v ] + 1>mid 则说明这条边不满足,加入新图里面。

在新图上跑一边必经点,如果必经点只有一个,并且这个点删掉后,断了的链不会再大于mid,则满足条件。

(因为前面一直深陷于一种很神奇的做法,所以没有打二分,就不发代码了。。。因为这道题把好多人都问爆了,真的对不起他们。。。唉。。。

原文地址:https://www.cnblogs.com/mowanying/p/11815470.html