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