卧薪尝胆，厚积薄发。
Formula 1
Date: Wed Oct 17 17:15:13 CST 2018
In Category:
Description：
给一个图，起点，终点，路上有若干加油站，求最小的油箱大小使得能在不缺油的情况下从起点到终点。
$1\leqslant n\leqslant 10^5$
Solution：
第一个思路可以二分油箱大小，设
$d[i]$
表示到
$i$
还剩的最大油量，然后跑
$SPFA$
。
第二个思路是把边拆出一个点来，然后多源
$BFS$
，并用并查集判断起点终点是否连通。
之所以要拆点是因为如果不拆点可能更新顺序会影响答案，比如取出来一个
$6$
，更新了一圈
$7$
，然后又取出来一个
$6$
，然后两个
$7$
接上了，但实际一个
$6$
和一个
$7$
更优。
In tag:
图论-BFS
Timeline
About
Toolbox
Friends
Copyright © 2020
wjh15101051
ღゝ◡╹)ノ♡