FoxTheLinguist

作者:孙奕灿

关键词:最小树形图

问题简述

有 $N$ 门课,每门课有 $Level~0\sim Level~9$,一开始你会每门课的 $0$ 级,有 $M$ 种训练,每种训练可以描述为 “在你学会了 $A$ 的 $Level~B$ 之后,可以花 $T$ 的时间学会 $C$ 的 $Level~D$”,当然,当你某门课学会了某个等级,那么这门课之前的等级都可以视为学会,问所有课到达 $9$ 级的最短时间,或说明不可能.

数据范围

$N\leq 9$

$M\leq 200$

算法一

对每门课建立9个点, 分别对应其等级。我们把第 $i$ 门课的第 $j$ 个等级对应的点称为 $(i,j)$。

然后对每次训练,找到对应的两个点 $(A,B)$ 和 $(C,D)$,从 $(A,B)$ 向 $(C,D)$ 连一条权重为 $T$ 的有向边。

然后对于每个 $(i,j)$, 使其向 $(i,j-1)$ 连一条边权为 $0$ 的有向边。表示某门课学会了某个等级,那么这门课之前的等级都可以视为学会。

最后建立一个源点 $S$ ,向每门课的第 $0$ 级别连一条边权为 $0$ 的有向边。表示一开始你会所有课的 $0$ 级水平.

然后问题就变成找一个 $S$ 为根的外向树,使得边权和最小。

这是一个有向图的最小树形图的模型,可以使用经典的朱-刘算法在 $O(VE)$ 的时间内解决。

时间复杂度 $O(NM)$ 。