預備知識

f(u,v)$f(u,v)$表示u->v這條邊的實際流量 b(u,v)$b(u,v)$表示u->v這條邊的流量下界 c(u,v)$c(u,v)$表示u->v這條邊的流量上界 在一個無源匯的普通網絡流圖中，滿足

分別稱為流量限制條件和流量平衡條件 而在有上下界的網絡流圖中，由于多了流量下界b(u,v)$b(u,v)$的限制，滿足

無源匯可行流

建圖方法

將有上下界的網絡流圖轉化成普通的網絡流圖

求解方法

在新圖上跑ss到tt的最大流 若新圖滿流，那么一定存在一種可行流 此時，原圖中每一條邊的流量應為新圖中對應的邊的流量+這條邊的流量下界

證明

在原圖中，假設每條邊的實際流量為f(u,v)=b(u,v)+g(u,v)$f(u,v)=b(u,v)+g(u,v)$ 其中g(u,v)≤c(u,v)?b(u,v)$g(u,v)/le c(u,v)-b(u,v)$

我們可以將原圖中的邊改為上界為c(u,v)?b(u,v)$c(u,v)-b(u,v)$的邊，變成一個普通的網絡流圖 經過以上的改造，g(u,v)$g(u,v)$實際上是新圖中邊u->v的實際流量，原圖中的實際流量f(u,v)=b(u,v)+g(u,v)$f(u,v)=b(u,v)+g(u,v)$ 但是如果在這個新圖中直接求可行流的話是錯誤的

舉個栗子 原圖 按照上面的方法改造過的新圖 這個圖的可行流為1，還原成原圖的實際流量為 很顯然滿足流量限制條件，但是不滿足流量平衡條件 即∑g(u,i)≠∑g(i,v)$/sum g(u,i)/ne /sum g(i,v)$

由于需要滿足流量平衡條件 ∑f(u,i)=∑f(i,v)$/sum f(u,i)=/sum f(i,v)$ ∑[b(u,i)+g(u,i)]=∑[b(i,v)+g(i,v)]$/sum[b(u,i)+g(u,i)]=/sum[b(i,v)+g(i,v)]$ ∑b(u,i)?∑b(i,v)=∑g(i,v)?∑g(u,i)$/sum b(u,i)-/sum b(i,v)=/sum g(i,v)-/sum g(u,i)$ 令d(i)=∑b(u,i)?∑b(i,v)$d(i)=/sum b(u,i)-/sum b(i,v)$ 當d(i)>0$d(i)>0$時 ∑g(i,v)=∑g(u,i)+d(i)$/sum g(i,v)=/sum g(u,i)+d(i)$ 所以需要一條邊流量為d(i)$d(i)$來補流 當d(i)<0$d(i)<0$時 ∑g(u,i)=∑g(i,v)+[?d(i)]$/sum g(u,i)=/sum g(i,v)+[-d(i)]$ 所以需要一條邊流量為d(i)$d(i)$來分流 可以發現，添加的所有與附加源點或者附加匯點相連的邊必須滿流，原圖才有可行流 證畢

有源匯可行流

建圖方法

在原圖中添加一條邊t->s，流量限制為[0,inf] 即讓源點和匯點也滿足流量平衡條件 這樣就改造成了無源匯的網絡流圖 其余方法同上

求解方法

同 無源匯可行流

證明

同 無源匯可行流

有源匯最大流

建圖方法

同有源匯可行流

求解方法

在新圖上跑ss到tt的最大流 若新圖滿流，那么一定存在一種可行流 記此時∑f(s,i)=sum1$/sum f(s,i)=sum_1$ 將t->s這條邊拆掉，在新圖上跑s到t的最大流 記此時∑f(s,i)=sum2$/sum f(s,i)=sum_2$ 最終答案即為sum1+sum2$sum_1+sum_2$

證明

添加附加源匯的作用：為了滿足流量平衡條件，在新圖中進行相應的補流或分流 只要連接附加源匯的邊滿流，新圖中s->t的任意一種可行流都是原圖的可行流 跑ss->tt的最大流了之后，相當于是使連接附加源匯的邊滿流，進而求出了一種可行流 再將t->s的邊拆掉（使s->t變成一個有源匯的網絡流圖），跑s到t的最大流，加上跑出來的最大流即為原圖中一種可行的最大流

有源匯最小流

建圖方法

同 無源匯可行流

求解方法

求ss->tt最大流 連邊t->s,inf 求ss->tt最大流 答案即為邊t->s,inf的實際流量

證明

第一遍做的時候并無t->s這條邊，所以s->t的流量已經盡力往其它邊流了 加上t->s這條邊后，流過這條邊的都是些剩余的流不到其他邊的流量，從而達到盡可能減少T->S這邊上的流量的效果，即減小了最終答案。

有源匯費用流

建圖方法

將有上下界的網絡流圖轉化成普通的網絡流圖

求解方法

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

證明

注意： 有上下界的費用流指的是在滿足流量限制條件和流量平衡條件的情況下$/color{red}{滿足流量限制條件和流量平衡條件的情況下}$的最小費用流 而不是$/color{red}{而不是}$在滿足流量限制條件和流量平衡條件并且滿足最大流$/color{red}{最大流}$的情況下的最小費用流 也就是說，有上下界的費用流只需要滿足網絡流的條件就可以了，而普通的費用流是滿足一般條件并且滿足是最大流的基礎上的最小費用

證明同 有源匯的可行流

小結

重點理解“補流”和“分流”的作用 注意流的“等效”