上下界最大流,最小流

渐渐 posted @ 2010年9月26日 09:39 in ACM-算法学习 with tags 最大流,最小流 , 3041 阅读

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

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)

Avatar_small
maid services dubai 说:
2019年9月28日 13:30

This sofa from the living room would be the most beautiful furniture and the place where most air-borne pollutants hide. Cargo area bugs, microbes, dust dust etc will probably contaminate ones sofa. That's why sofa clean-up services are really important. National Emirates would be the leading furniture cleaning service agency in Abu Dhabi and your furniture from to be a hiding spot for bacterias and microbes. <a href="https://www.springcleaning.ae/">maid services dubai</a>

Avatar_small
handi sports 说:
2019年11月18日 16:24

Credit card debt financing is just about the most common solution to finance your organization. You sign up for a bank loan and consent to repay over a lot of time. The financial institution charges attention and tends to make a profit like that. The most frequent business lenders will be the following:


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter