上下界最大流,最小流

这里只记录一下最大,最小流求法,暂不写理论证明

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)