OceanEye's Blog

是时候表演真正的技术了!

@OceanEye9月前

08/30
16:52
OI

BZOJ3832

思路清奇的一道题
首先有向图的最长链可以通过添加超级源超级汇,计算超级源超级汇之间的最长路来实现
如果仅仅如此并不足以做这道题
这道题还用了最小割的思想
看大佬题解吧……不是很清楚这题要怎么讲明白

大佬题解的传送门

\(S\) 为超级源
\(T\) 为超级汇
\(g[i] \) 为 \(S\) 到 \(i\) 的最长路
\(f[i] \) 为 \(i\) 到 \(T\) 的最长路
\( edge={ From,To } \)
令一条边存在的贡献为 \( g[From]+f[To]+1 \)
这是这条边对最长路的贡献
我们维护两个点集 \( A,B \) 。一开始 \( A \) 中只有S,其余点都在 \(B\) 中。
我们用数据结构来维护两个集合之间的连边,注意这是一定包括了所有能从S到T的路径的。每次我们按照昂拓扑序从B中拿点到A中,在这个过程中维护边集即可
令被移动的点为 \(x\)
那么我们需要先把从 \(A\) 到 \(x\) 的边全部删除,即删除 \(x\) 的所有入边 【为什么?我们之前用的是拓扑序啊不是吗】
完成统计后再将 \(x\) 到 \(B\) 的边全部加入即可
同时为了保证一个点在被删除后,两端的点依然有贡献,我们要在一开始加入 \(f[x]\)
后面点 \(x\) 从B移动到A后,我们要把 \(f[x]\) 删除,再将 \(g[x]\) 加入边集。
某次删点之后我们选出来的边的贡献值中最大的最小,那么这就是我们要求的答案
值的维护随便挑个数据结构就做了
难点是边的值要怎么去想到
【算了反正我也是看题解的记住这个思路就好了】

代码:

BZOJ3832