首页 > 代码库 > zoj 2314 无源无汇有上下限的可行流

zoj 2314 无源无汇有上下限的可行流

Mi= sum(i点所有流进来的下界流)– sum(i点所有流出去的下界流)

如果Mi大于0,代表此点必须还要流出去Mi的自由流,那么我们从源点连一条Mi的边到该点。

如果Mi小于0,代表此点必须还要流进来Mi的自由流,那么我们从该点连一条Mi的边到汇点。

如果求S->T的最大流,看是否满流(S的相邻边都流满)。

满流则有解,否则无解。

 

zoj 2314 无源无汇有上下限的可行流