上下界最大流,最小流
这里只记录一下最大,最小流求法,暂不写理论证明
1.新源S'给每个点加一条容量为《流入的下界总和》的边
2.新汇T'给每个点加一条容量为《流出的下界总和》的边。
若最小流:
求一次S'->T'最大流,T->S add inf 再求一次 S'->T'最大流
若满流,可行
T->S的流量为最小流,各边流量+下界为最小流各边实际流量
若最大流:
T->S add inf 求一次最大流
若满流,可行
去掉T->S的边(我感觉用sap应该不要去也可以??待验证 (成功一次,理论上没问题))
求S->T最大流,结果为最大流,各边流量+下界为最大流实际流量
ps:如果是无源无汇的话,直接求一次最大流就可以了
(待纠错,mark)