巧妙的使用满流的特性解决问题。

对每一天,连一条容量为 $INF - 需求人数$ 的边,对于补充的人连一条容量为 $INF$ ,花费为价格的边。

对这个图跑最小费用最大流,其中最大流一定是 $INF$ ,最小费用即答案。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×