無源匯有上下界可行流

法一（據(jù)說適合點(diǎn)少邊多的圖）：

建圖方法

• 首先建立附加源點(diǎn)ss和附加匯點(diǎn)tt
• 對(duì)于原圖中的邊x->y，若限制為[b,c]，那么連邊x->y，流量為c-b
• 對(duì)于原圖中的某一個(gè)點(diǎn)i，記d(i)為流入這個(gè)點(diǎn)的所有邊的下界和減去流出這個(gè)點(diǎn)的所有邊的下界和

若d(i)>0，那么連邊ss->i，流量為d(i)

若d(i)<0，那么連邊i->tt，流量為-d(i)

求解方法

• 在新圖上跑ss到tt的最大流
• 若新圖滿流，那么一定存在一種可行流
• 此時(shí)，原圖中每一條邊的流量應(yīng)為新圖中對(duì)應(yīng)的邊的流量+這條邊的流量下界

法二（據(jù)說適合點(diǎn)多邊少的圖）：

建圖方法

• 首先建立一個(gè)源點(diǎn)ss和一個(gè)匯點(diǎn)tt，一般稱為附加源和附加匯。
• 對(duì)于圖中的每條弧<u,v>，假設(shè)它容量上界為c，下界b，那么把這條邊拆為三條只有上界的弧。

一條為<ss,v>，容量為b；

一條為<u,tt>，容量為b；

一條為<u,v>，容量為c?b。

（其中前兩條弧一般稱為附加弧。）

求解方法

• 以ss為源點(diǎn)，以tt為匯點(diǎn)，對(duì)這張圖跑最大流。
• 如果所有的附加弧都滿流，則原圖有可行流。
• 這時(shí)，每條非附加弧的流量加上它的容量下界，就是原圖中這條弧應(yīng)該有的流量。

理解方法

對(duì)于原圖中的每條弧，我們把c?b稱為它的自由流量，意思就是只要它流滿了下界，這些流多少都沒問題。

既然如此，對(duì)于每條弧<u,v>，我們強(qiáng)制給v提供b單位的流量，并且強(qiáng)制從u那里拿走b單位的流量，這一步對(duì)應(yīng)著兩條附加弧。

如果這一系列強(qiáng)制操作能完成的話，也就是有一組可行流了。

注意：這張圖的最大流只是對(duì)應(yīng)著原圖的一組可行流，而不是原圖的最大或最小流。

有源匯有上下界可行流

建圖方法

• 在原圖中添加一條邊t->s，流量為inf
• 其余建圖方法與無源匯有上下界可行流相同

求解方法

• 同無源匯有上下界可行流
• 弧<t,s>的流量就是原圖的總流量

理解方法

有源匯相比無源匯的不同就在于，源和匯是不滿足流量平衡的，那么連接<t,s>之后，源和匯也滿足了流量平衡，就可以直接按照無源匯的方式建模。

注意：這張圖的最大流只是對(duì)應(yīng)著原圖的一組可行流，而不是原圖的最大或最小流。

有源匯有上下界最大流

建圖方法

• 同有源匯有上下界可行流

求解方法

• 在新圖上跑ss到tt的最大流
• 若新圖滿流，那么一定存在一種可行流
• 記此時(shí)∑f(s,i)=sum1 ，即此時(shí)t->s的最大流，也就是求反向邊s->t的流量
• 將t->s這條邊拆掉，在新圖上跑s到t的最大流
• 記此時(shí)∑f(s,i)=sum2 ，即maxflow（s，t）
• 最終答案即為sum1+sum2

理解方法

為什么要在已經(jīng)有了流量的圖上跑最大流？因?yàn)槟菑垐D保證了每條弧的容量下界，在這張圖上跑最大流，實(shí)際上就是在容量下界全部滿足的前提下盡量多得獲得“自由流量”。

有源匯有上下界最小流

建圖方法（常用的一種）

• 按照有源匯可行流的方法建圖，但是不要建立<t,s>這條弧。

求解方法

• 求ss->tt最大流
• 連邊t->s,inf
• 求ss->tt最大流
• 若滿流，則存在可行流，答案即為邊t->s,inf的實(shí)際流量

理解方法

在跑完有源匯可行流之后，弧<t,s>的流量就是原圖的流量。

第一遍做的時(shí)候并無t->s這條邊，所以s->t的流量已經(jīng)盡力往其它邊流了。

加上t->s這條邊后，流過這條邊的都是些剩余的流不到其他邊的流量，從而達(dá)到盡可能減少t->s這條邊上的流量的效果，即減小了最終答案。

注意：最小流判斷是否有可行解的位置與時(shí)機(jī)與另外幾種上下界網(wǎng)絡(luò)流的不同！

有源匯有上下界費(fèi)用流

法一（據(jù)說適合點(diǎn)少邊多的圖）：

建圖方法

• 首先建立附加源點(diǎn)ss和附加匯點(diǎn)tt
• 對(duì)原圖中某邊x->y，若限制為[b,c]，費(fèi)用為cost，那么連邊x->y，流量為c-b，費(fèi)用為cost
• 對(duì)原圖中某點(diǎn)i，記d(i)為流入這個(gè)點(diǎn)的所有邊的下界和減去流出這個(gè)點(diǎn)的所有邊的下界和

若d(i)>0，那么連邊ss->i，流量為d(i)，費(fèi)用為0

若d(i)<0，那么連邊i->tt，流量為-d(i)，費(fèi)用為0

• 連邊t->s，流量為inf，費(fèi)用為0

求解方法

• 跑ss->tt的最小費(fèi)用最大流
• 答案即為（求出的費(fèi)用+原圖中邊的下界*邊的費(fèi)用）

法二（據(jù)說適合點(diǎn)多邊少的圖）：

建圖方法

• 首先建立附加源ss和附加匯tt。
• 對(duì)于圖中的每條弧<u,v>，假設(shè)它容量上界為c，下界b，費(fèi)用為cost那么把這條邊拆為三條只有上界的弧。

一條為<ss,v>，容量為b，費(fèi)用為0；

一條為<u,tt>，容量為b，費(fèi)用為0；

一條為<u,v>，容量為c?b，費(fèi)用為cost。

求解方法

• 跑從ss到tt的費(fèi)用流
• 答案即為（求出的費(fèi)用+原圖中邊的下界*邊的費(fèi)用）

總結(jié)

以上是生活随笔為你收集整理的有上下界网络流问题汇总的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。