OceanEye's Blog

很多人即使只见过一面,已经算见过了最后一面。

BZOJ1497

最小割

从源点向每个人连收益大小的边

人向站连大小为INF的边

站向汇连大小为成本的边

这个时候的割有三种情况:

1.把收益割掉了,此时支出>收入

2.把支出割掉了,此时支出<收入

3.支出和收入同时割掉了,支出=收入

总的答案就是sum-割