如果你出现负圈
查看原帖
如果你出现负圈
484910
SwordDance楼主2024/7/28 18:27

主要是两者建边方式:

1.每加入一道新的菜品,将这道菜品与目前所有厨师建边,然后扩展新厨师。

2.先将所有菜品与初始厨师建边,然后每轮增广后扩展新厨师。

前者会出现负圈,后者不会。

这是因为前者存在先跑最优流后,加入新菜品存在更优流的情况,此时就会出现负圈。

而后者每轮增广一定是最优流,而加入新厨师后,边权代价递增,一定不会出现更优流,所以已经不会出现负圈。

希望能帮到大家。

2024/7/28 18:27
加载中...