P3573
P3573 [POI2014] RAJ-Rally
P3573 [POI2014] RAJ-Rally 题意 给一张 \(DAG\),问删去一个点的最长路是多少。 题解 好妙的题。 考虑对于每个点求出删除此点之后的最长路。 考虑到一个 \(DAG\) 只会由拓扑序低的点走向高的点。 所以我们按照拓扑序枚举点删除之后的最短路。 考虑根据当前点的拓扑序将 ......
P3573 [POI2014]RAJ-Rally
网瘾犯了。 https://www.luogu.com.cn/problem/P3573 题意:在 DAG 上删除一点,使得剩下点的最长路最短。 解答:用 $f_v$ 和 $h_v$ 表示终点为 $v$、起点为 $v$ 的单源最长路。按照拓扑序(这样才是 DAG,有 dp 性质)枚举 $u$,每次先 ......