Open teekaytai opened 5 months ago
Instead of updating total_cost once for each edge with total_cost += pushed * cost, we can update the total_cost once per augmenting path with total_cost += f * d[t], since every path to the sink in the level graph has the same total cost.
total_cost
total_cost += pushed * cost
total_cost += f * d[t]
Instead of updating
total_cost once for each edge withtotal_cost += pushed * cost, we can update thetotal_cost once per augmenting path withtotal_cost += f * d[t], since every path to the sink in the level graph has the same total cost.