3573

P3573 [POI2014] RAJ-Rally 题意 给一张 \(DAG\)，问删去一个点的最长路是多少。 题解 好妙的题。 考虑对于每个点求出删除此点之后的最长路。 考虑到一个 \(DAG\) 只会由拓扑序低的点走向高的点。 所以我们按照拓扑序枚举点删除之后的最短路。 考虑根据当前点的拓扑序将 ......

网瘾犯了。 https://www.luogu.com.cn/problem/P3573 题意：在 DAG 上删除一点，使得剩下点的最长路最短。 解答：用 $f_v$ 和 $h_v$ 表示终点为 $v$、起点为 $v$ 的单源最长路。按照拓扑序（这样才是 DAG，有 dp 性质）枚举 $u$，每次先 ......

非常好题目，爱来自 xc。 看到有向无环图，想到拓扑序。通过拓扑序，可以轻松求出以每个点为起点的最长路 $disS$与每个点为终点的最长路 $disF$。 如何求总共的最长路？在 $disS,disF,disS_u + 1 + disF_v((u,v)\in E)$ 中取最大值即可。注意最后一项，表 ......