Simple (?) Min-Cost Max-Flow◮ Forge

Simple (?) Min-Cost Max-Flow
◮ Forget about the costs and just find a max-flow
◮ Repeat:
– Take the residual graph
– Find a negative-cost cycle using Bellman-Ford
◮ If there is none, finish
– Circulate flow through the cycle to decrease the total cost,
until one of the edges is saturated
◮ The total amount of flow doesn’t change!
◮ Time complexity: very slow

ผลลัพธ์ (ไทย) 1:

ง่าย ๆ (?) กระแสสูงสุดต้นทุนต่ำสุด◮ลืมเกี่ยวกับต้นทุนและก็พบกับกระแสสูงสุด◮ซ้ำ:– ใช้กราฟส่วนที่เหลือ– ค้นหาวงจรลบต้นทุนที่ใช้บริการฟอร์ด◮ถ้ามีไม่มี เสร็จสิ้น-การไหลเวียนกระแสผ่านวงจรเพื่อลดต้นทุนรวมจนกว่าขอบหนึ่งจะอิ่มตัว◮ยอดรวมของกระแสไม่เปลี่ยนความซับซ้อนเวลา◮: ช้า

ผลลัพธ์ (ไทย) 3:

ง่าย ( ? ) มินราคา◮แม็กซ์ไหล
ลืมเกี่ยวกับค่าใช้จ่ายและหาแม็กซ์ไหล

) ◮ย้ำใช้–กราฟ
ที่เหลือหาวงจรต้นทุนลบโดยใช้พนักงานฟอร์ด
◮หากไม่มี จบ
- หมุนเวียนไหลผ่านวงจรเพื่อลดต้นทุนรวม
จนกว่าหนึ่งขอบคือ อิ่มตัว
◮ยอดรวมของการไหลไม่เปลี่ยน
◮ความซับซ้อน : ช้ามากเวลา