柒葉灬 的博客

柒葉灬 的博客

「JOISC 2014 Day2」水壶

posted on 2019-01-11 10:10:21 | under 赛后题解 |

「JOISC 2014 Day2」水壶


子任务 $1$ :

暴力求出每两个点之间的最小代价,

用 $Floyd$ 求出每两个点之间的最小代价。


$100$ pts:

理想情况下,如果我们知道每两个点之间的最小距离,

能在 $log$ 的时间里面解决吗?

显然不能。

所以肯定不是求每两个点之间的最小距离。


这题有一个特殊的地方,

求的是边的最大值

那我们希望用最短的边构成一个连通图,

显然想到构造最小生成树啊。

所以 $bfs$ 一遍,把所有的点塞入队列

每次到达一个点的时候标记,并记录距离和这个点的 $id$

造了最小生成树(注意可能是森林)之后,

$dfs$ 之后倍增求解即可。