上下界網(wǎng)絡(luò)流可以看做普通網(wǎng)絡(luò)流的升級版，現(xiàn)在對于流量網(wǎng)絡(luò)，我們不再只關(guān)注其流量的上界，而是同時(shí)關(guān)注流量的上下界。

一、無源匯有上下界可行流

這是上下界網(wǎng)絡(luò)流中最簡單的一種，給定一個(gè)沒有源點(diǎn)和匯點(diǎn)、每條邊的流量有上下界的流量網(wǎng)絡(luò)，問是否存在一種可行流使得流量平衡。

做法是，我們把它拆成兩個(gè)結(jié)構(gòu)與原圖相同的普通網(wǎng)絡(luò)，一個(gè)每條邊的容量為原網(wǎng)絡(luò)對應(yīng)邊的流量下界，另一個(gè)為對應(yīng)邊的流量上界與下界之差。

我們希望下界網(wǎng)絡(luò)和差網(wǎng)絡(luò)的流相加后恰好是原圖的一個(gè)可行流，這首先要求下界網(wǎng)絡(luò)是滿流的（可行流必須達(dá)到每條邊的下界）。但是下界網(wǎng)絡(luò)滿流后不一定流量平衡，所以我們要對差網(wǎng)絡(luò)進(jìn)行一定的修改以彌補(bǔ)這種不平衡。

我們分別考慮下界網(wǎng)絡(luò)的每個(gè)點(diǎn)。A點(diǎn)，流入量為3，流出量也為3，所以是平衡的，那么在差網(wǎng)絡(luò)中，也應(yīng)該是平衡的，所以不做修改。B點(diǎn)，流入量為3，流出量為1，流入比流出多2，所以我們希望在差網(wǎng)絡(luò)中，B的流出應(yīng)該比流入多2，于是我們在差網(wǎng)絡(luò)中新設(shè)一個(gè)源點(diǎn)，然后加入一條容量為2的附加邊從源點(diǎn)連向B，這樣在差網(wǎng)絡(luò)平衡時(shí)，除去附加邊，B點(diǎn)的流出恰好比流入多2，C點(diǎn)與B點(diǎn)類似。D點(diǎn)則相反，因?yàn)槲覀兿Ｍ诓罹W(wǎng)絡(luò)中D點(diǎn)流入比流出多2，所以我們新設(shè)一個(gè)匯點(diǎn)，然后從D點(diǎn)連一條容量為2的附加邊到匯點(diǎn)，E點(diǎn)又和D類似。

也就是說，如果下界網(wǎng)絡(luò)中某個(gè)點(diǎn)有x的凈流入，在差網(wǎng)絡(luò)中我們就從源點(diǎn)向它連一條容量為x的附加邊；相反，如果下界網(wǎng)絡(luò)中某個(gè)點(diǎn)有x的凈流出，在差網(wǎng)絡(luò)中我們就從它向匯點(diǎn)連一條容量為x的附加邊。這樣，我們把差網(wǎng)絡(luò)修改如下：

在差網(wǎng)絡(luò)上跑一遍最大流，把每條非附加邊的流，加上下界網(wǎng)絡(luò)的滿流，就是一個(gè)可行流。但是，如果跑完最大流發(fā)現(xiàn)，存在附加邊未滿流，那說明平衡條件沒有得到滿足，于是原圖不存在可行流。

在實(shí)際中，是不需要建立下界網(wǎng)絡(luò)的，只需要對差網(wǎng)絡(luò)進(jìn)行操作即可。另外最后判斷的時(shí)候并無必要遍歷所有附加邊，而只需要判斷所有從源點(diǎn)出發(fā)的邊，或者判斷所有連向匯點(diǎn)的邊即可，因?yàn)楦鶕?jù)網(wǎng)絡(luò)流的性質(zhì)，兩者容量和應(yīng)該相等，于是它們要么都滿流，要么都不滿流。

二、有源匯有上下界可行流

從匯點(diǎn)到源點(diǎn)連一條下界為0，上界為的附加邊，得到一張和原圖等價(jià)的無源匯流量網(wǎng)絡(luò)，于是轉(zhuǎn)化成了無源匯有上下界可行流問題。此時(shí)從源點(diǎn)到匯點(diǎn)的可行流流量，即為從匯點(diǎn)到源點(diǎn)的那條附加邊的流量（注意下界網(wǎng)絡(luò)中對應(yīng)邊流量為0）。

注意，這時(shí)候原來的源點(diǎn)和匯點(diǎn)已被處理成普通點(diǎn)，和之后差網(wǎng)絡(luò)需要額外建立的源、匯點(diǎn)是不同的點(diǎn)，之后如果這兩者同時(shí)出現(xiàn)，我們記前者為S、T，后者為S′、T′。

三、有源匯有上下界最大流

按照上一節(jié)的方法，我們已經(jīng)得到了一個(gè)可行流，且知道它的流量就是T到S的附加邊的流量。

要求從S到T的最大流，我們可以在差網(wǎng)絡(luò)中把所有附加邊刪除，然后以S與T為源點(diǎn)與匯點(diǎn)，再求殘余網(wǎng)絡(luò)的最大流，加上可行流的流量即為原網(wǎng)絡(luò)的最大流。這是因?yàn)椋尚辛饕呀?jīng)保證了流量平衡，那么刪去附加邊后，我們再跑一次最大流把殘余網(wǎng)絡(luò)“榨干”，最后得到的流仍保證是平衡的。

當(dāng)然實(shí)際上S'與T'連接的附加邊不需要?jiǎng)h，這種出度或入度為0、又非源匯點(diǎn)的點(diǎn)是不影響最大流的，何況如果存在可行流，它們的殘余容量已經(jīng)為0了。