主要是两者建边方式:
1.每加入一道新的菜品,将这道菜品与目前所有厨师建边,然后扩展新厨师。
2.先将所有菜品与初始厨师建边,然后每轮增广后扩展新厨师。
前者会出现负圈,后者不会。
这是因为前者存在先跑最优流后,加入新菜品存在更优流的情况,此时就会出现负圈。
而后者每轮增广一定是最优流,而加入新厨师后,边权代价递增,一定不会出现更优流,所以已经不会出现负圈。
希望能帮到大家。