题目链接
题解
神思路orz,根本不会做
设\(f[i]\)为到\(i\)的最长路,\(g[i]\)为\(i\)出发的最长路,二者可以拓扑序后\(dp\)求得
那么一条边
\((u,v)\)的对应的最长链就是
\(f[u] + 1 + g[v]\) 我们人为加入源汇点
\(S\),
\(T\),
\(S\)向每个点连边,每个点向
\(T\)连边
我们考虑把整个图划分开
一开始所有点都在
\(T\)这边,割边为所有
\(S\)的边
然后我们按照拓扑序把点逐一加入
\(S\)集合中
加入时,我们删去
\(S\)集合连向该点的边,然后询问所有边的最大值,即为删去该点的最长链
加入后,我们加入该点连向
\(T\)集合的边
由于是按照拓扑序,所以以上提到的所有边就是该点的所有入边/出边
然后所有边的最大值可以用堆或者线段树维护
#include #include #include #include #include #include #include
转载地址:https://blog.csdn.net/weixin_30810239/article/details/98612048 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!