有的時(shí)候，網(wǎng)絡(luò)流建模要考慮某些邊必須選擇若干次，又不能多于若干次，而且不太容易轉(zhuǎn)化成比較好的限制模型，

就簡單粗暴地給每條邊定一個(gè)流量的上下界，求在滿足上下界的基礎(chǔ)上的一些問題。

大概有以下幾種。

基本思路都是先滿足下界，再調(diào)整流量守恒，一邊滿足最優(yōu)性。

?

無源匯上下界可行流

每條邊的流量有上下界
問是否存在一種可行方案

?

首先我們要保證每個(gè)點(diǎn)的流入流量等于流出流量
如果存在一個(gè)可行流,那么一定滿足每條邊的流量都大于等于流量的下限.因此我們可以令每條邊的流量等于流量下限,得到一個(gè)初始流,然后建出這個(gè)流的殘量網(wǎng)絡(luò)，每條邊的流量等于上限減下限。
但現(xiàn)在可能流量不是守恒的，讓t[i]=流入量-流出量
我們建出虛擬的源點(diǎn)和匯點(diǎn)，如果t[i]>0,源點(diǎn)向i連t[i]的邊，否則i點(diǎn)向匯點(diǎn)連-t[i]的邊，看是否滿流即可

?

注意，把下界干掉時(shí)，不是真的流過去，反向邊不用動(dòng)。因?yàn)檫@里不能反悔。

?

有源匯上下界可行流

T到S連一條inf的邊e。然后同上。

設(shè)e的最終流量是w，則原圖的可行流就是w

證明：

S，T本身沒有入邊、出邊，那么e的流量就是S流出的，流到T的流量。

拆掉這個(gè)邊，每個(gè)邊流量加上下界

由于剩下的圖中，滿足流量守恒和上下界，那么一定是一個(gè)合法的網(wǎng)絡(luò)流流量分配，那么S流出的流量w就是總流量

?

無源匯上下界最小費(fèi)用可行流

干掉下界的時(shí)候，把費(fèi)用先計(jì)算上。

把超級(jí)源超級(jí)匯求最大流的一步，換成最小費(fèi)用最大流即可。

即滿足合法的前提下，最小化費(fèi)用。

費(fèi)用就是之前的費(fèi)用加上這次的費(fèi)用。

例題：[NOI2008]志愿者招募

?

有源匯上下界最小費(fèi)用可行流

t到s是（inf，0）的邊。

同上。

?

有源匯上下界（最小費(fèi)用）最大流

先求可行流

現(xiàn)在流量已經(jīng)守恒了。

拆掉t到s的邊

殘量網(wǎng)絡(luò)上求s到t的最大流即可。

因?yàn)樽畲罅鬟^程一定滿足流量守恒，所以依然合法。所以求可行流的反向邊流量可以保留，支持反悔。

最大流=可行流+s到t的增加的最大流

?

如果涉及最小費(fèi)用，把所有的最大流換成最小費(fèi)用最大流即可。

記得統(tǒng)計(jì)三次費(fèi)用。

?

有源匯上下界（最小費(fèi)用）最小流

https://blog.csdn.net/Hanks_o/article/details/77995557

兩種方法。

第一種：

直接類比上面的 有源匯上下界（最小費(fèi)用）最大流

理解一下反邊，就是反悔。

t到s的最大流，就是s到t能減少的最多的流量。

所以最后一步，求t到s的最大流。

最小流=可行流-t到s的最大流。

?

第二種：（并不如第一個(gè)好理解）

類似 <有源匯上下界可行流> 的構(gòu)圖方法，但是不添加T到S的邊，求一次超級(jí)源到超級(jí)匯的最大流。
加邊(T,S,0,+∞)，在上一步殘量網(wǎng)絡(luò)基礎(chǔ)上再求一次超級(jí)源到超級(jí)匯的最大流。
流經(jīng)T到S的邊的流量就是最小流的值。

該算法的思想是在第一步中盡可能填充循環(huán)流，以減小最小流的代價(jià)。

第二步最大流為了保證合法性。

其實(shí)相當(dāng)于，第一步先占據(jù)一些循環(huán)流，然后再跑完第二個(gè)最大流之后，刪掉t到s的邊，對(duì)于一些第一步構(gòu)成的循環(huán)流，刪掉。

觀察現(xiàn)在實(shí)際的圖流量分配，就是最小流了。

?

例題： P4843 清理雪道

?

轉(zhuǎn)載于:https://www.cnblogs.com/Miracevin/p/10132570.html

總結(jié)

以上是生活随笔為你收集整理的[学习笔记]上下界网络流的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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