网络流重制版：最大流Dinic，以及EK、Dinic时间复杂度的证明（含坑）
目錄前言關于最大流神奇的術語EK算法Dinic時間復雜度EKDinic細節與一些神奇的性質反向弧的作用以及代碼邊中的c合法的f對應流st有入邊，ed有出邊雙向邊的兩種處理方法s＜f優化反向邊本次無用性Dinic深度嚴格單調遞增性從起點跑和從終點跑反向邊處理方法當前弧優化參考資料坑
前言
初三的時候就知道以后注定會重新寫網絡流的博客了。
但是呢，之前的博客是不會刪的。水數量
因為之前碰了很多雜七雜八的東西。
萬一刪了不就前功盡棄了，如果有少數幾個讀得懂我所寫的文章的，可以結合兩篇一起看，遇到重復的地方以這篇為參考，加上自己的理解。
需要注意的是，這篇文章可能對于信息學新手不會太友好，如果你只是個新手，建議去看看我之前的那篇，那篇提供了一個例子的講解，會比較好，而這篇文章注重的是理論，比較干。說實話，就是懶得寫例子
當然，這篇文章寫的比較倉促，因為還要備戰NOIP。
關于最大流
最大流是啥？
想象一坨有向的水管，每個水管連接著兩個點，且圖中有個入水口，有個出水口，出水口可以無限出水，入水口可以瞬間收水。
但是呢，在一個單位時間，一個水管只能通過(c_{i})單位體積的水，同時水瞬間通過這個水管，并在同一個單位時間通過其余的水管，且水管不能存水，如果水不能通過這個水管一瞬間流到終點，那么水不會流過來。有生命的水
那么，一個單位時間內入水口最多入多少體積的水？這就是最大流問題。
其中(a/b)分別表示流過的水和最多流過多少的水，(A)為出水口，(E)為入水口。
可以看到，上面兩個就是同一個圖的最大流，有兩種，其中，為什么第一個圖中，(AC)流過的流量是(0)呢？因為如果從(A)點流出了一體積的水到了(C)又到了(D)，無法到達終點(E)，所以這一體積的水不會流過(C)，而是選擇留在原地。
當然，上述的表示非常的SB，因為我確實不知道如何比較規范的用中文表述。
我們用((i,j))表示一條邊，(c(i,j))表示這條邊最多流過的水的體積，(f(i,j))表示這條邊流過的水的體積。
那么有以下規定。
((i,j)∈E,0≤f(i,j)≤c(i,j),(i,j)?E,c(i,j)=0)
(sumlimits_{(x,i)∈E}f(x,i)=sumlimits_{(j,x)∈E}f(j,x)(x≠st,ed))
在(E)中，(st)不存在入邊，(ed)不存在出邊。（存在就刪了）
(sumlimits_{(st,i)∈E}f(st,i)=sumlimits_{(j,ed)∈E}f(j,ed))
然后要求最大化(sumlimits_{(st,i)∈E}f(st,i))。
這個時候就有人很敏銳的意識到，那是不是圖外面有個自環，這個自環也滿足要求？是的，沒錯，但是我們要求最大化(sumlimits_{(st,i)∈E}f(st,i))，這個環我們管不管無所謂。
神奇的術語
請注意：由于我的學習經常都是不學術的，所以這些術語的表達甚至意思可能與真實的術語有一定的偏差，見諒。但是應該不影響看這篇文章
弧：說白了就是有向邊。
反向弧：如果((x,y)∈E)，那么((y,x))就是((x,y))的反向弧。
我看算法導論的時候發現正規的網絡流定義(E)中的反向弧必須不屬于(E)，但是實際上如果屬于(E)也不會影響算法，但是呢，為了后面的表述方便，我們也是默認((y,x))不屬于(E)，但是如果題目要求呢？實際上我們有類似的轉換：
可以在不影響結果的情況下保證反向弧不在(E)中。
反向弧的(f,c)：((i,j)∈E,f(j,i)=-f(i,j),c(j,i)=0)，（有沒有人規定非(E)元素的(f)一定非負）。
網絡：就是點邊形成的有向圖，其中有意義的邊只有(E)和其反向弧。
流量網絡：網絡每條邊標出其(f)。
容量網絡：網絡每條邊標出其(c)。
殘余網絡：流量網絡(-)殘余網絡。（這里"(-)"的意思就是邊上標號相減）
增廣路徑：從(st)到(ed)的一條路徑，且路徑上的每條邊(f<c)，而這條路徑(p)的流量(f(p))就是路徑中(f-c)的最小值。
舉個例子：
當然，這里默認網絡中沒有意義的邊（比如殘余網絡中標號為(0)的邊，容量網絡中標號為(0)的邊）直接消失即可，畫圖方便一點。（updata：當然，在后面證明的過程中，我們會發現，這些容量流量都為(0)的邊沒有意義，不予討論，而且，在某些證明中，是只針對(f>0)的(E)的邊，在你發現證明看不懂的時候，或者存在很大的邏輯問題的時候，可以考慮看看是不是考慮了沒有意義的邊）
EK算法
這個算法是根據一個依據：網絡中不存在增廣路時就是最大流來搞的。
精髓就是每次只增廣最短的路徑（默認邊的長度都是(1)），因此只要不斷的跑分層圖，然后不斷增廣即可。
需要注意的是，一條邊的(f)改變時，其反向弧也要改變。
但是我沒有代碼QMQ，因為直接用Dinic的。
Dinic
我們發現，一次建圖就跑一條增廣路，真的是浪費！！！！
因此我們多跑幾次增廣路。
例題：https://www.luogu.com.cn/problem/P3376
代碼如下：
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
struct node
{
LL x,y,c/*還能流多少的流量*/,next,other/*反向弧的編號*/;
}a[250000];LL len,last[1300],st,ed,n,m;
void ins(LL x,LL y,LL c)
{
LL k1,k2;
len++;k1=len;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len;
len++;k2=len;
a[len].x=y;a[len].y=x;a[len].c=0;
a[len].next=last[y];last[y]=len;
a[k1].other=k2;
a[k2].other=k1;
}
LL list[1300],head,tail,h[1300];
bool bt_h()
{
memset(h,0,sizeof(h));h[st]=1;
list[1]=st;head=1;tail=2;
while(head!=tail)
{
LL x=list[head];
for(LL k=last[x];k>0;k=a[k].next)
{
LL y=a[k].y;
if(a[k].c>0 && h[y]==0)
{
h[y]=h[x]+1;
list[tail++]=y;
}
}
head++;
}
if(h[ed])return true;
else return false;
}
LL mymin(LL x,LL y){return x<y?x:y;}
LL findflow(LL x,LL f)
{
if(x==ed)return f;
LL s=0,t;
for(LL k=last[x];k>0;k=a[k].next)
{
LL y=a[k].y;
if(a[k].c>0 && h[y]==h[x]+1 && s<f/*沒有跑滿*/)
{
s+=(t=findflow(y,mymin(a[k].c,f-s)));
a[k].c-=t;a[a[k].other].c+=t;
}
}
if(s<f)h[x]=0;//如果這個點跑不滿，以后都不到這個點了
return s;
}
int main()
{
scanf("%lld%lld%lld%lld",&n,&m,&st,&ed);
for(LL i=1;i<=m;i++)
{
LL x,y,c;
scanf("%lld%lld%lld",&x,&y,&c);
ins(x,y,c);
}
LL s=0;
while(bt_h()==true)
{
s+=findflow(st,LL(999999999999));
}
printf("%lld
",s);
return 0;
}
時間復雜度
EK
事實上，對于(h[x])，不斷的增廣，(h[x])只會非嚴格單調遞增，設增廣后為(h')，增廣前在殘余網絡中有意義的邊構成的集合為(E)。
什么？如何證明？
我們設一次增廣后(h[x])減少了，且(x)是所有減少的點中(h')最小的點。
設(st)到(x)的路徑為(st?y→x)。
分類討論(y->x)。
如果((y,x)∈E)，(h[x]≤h[y]+1≤h[y]'+1≤h[y])。
如果((y,x)?E)，說明((x,y))是在增廣路徑中的，所以(h[x]=h[y]-1≤h[y]'-1,h[x]'=h[y]'+1≥h[x]+2)。
所以(h)單調遞增。
現在證明，一條增廣路徑(p)，如果一條邊在路徑上且(c-f)等于(f(p))，那么這條邊被稱為關鍵邊，本次增廣完之后便會在殘余網絡中沒有意義。
那么其重新有意義需要圖中帶來怎樣的變化呢？其重新有意義， 必須其反向弧存在于增廣路中。
即對于弧((x,y))，反向弧存在于增廣路中：(h[x]=h[y]-1,h[x]'=h[y]'+1≥h[y]+1≥h[x]+2)。
即要求(x)的深度加(2)，那么對于一條邊，其最多變成關鍵邊(frac{n-1}{2})次，所以時間復雜度就是：(O(nm^2))的。
但是需要注意的是，(x)的深度(+2)并不代表只讓一條邊有意義，比較容易陷入的誤區是：深度之和最多是(n^2)的，那么一個點深度(+2)不是只會讓一條邊有意義嗎？那不就是最多(frac{n^2}{2})次增廣。但是一個點深度(+2)不一定只讓一條邊有意義啊！！！！例子以后補。
當然，這也有個推論，只要我每次找到的增廣路都保證是圖中長度最小的，那么增廣路長度一定非嚴格遞增。
Dinic
(Dinic)時間復雜度為什么是正確的？依據(EK)算法的推論，我們可以在一次建分層圖的時候直接把本次分層圖中所有增廣路一下子找出來，這樣不就免了多次減分層圖的時間了嗎？
因此，時間復雜度還是(O(nm^2))的。（但事實上這是不是理論上界呢？不是說(n^2m)嗎？這個會在弧優化的時候具體分析）
細節與一些神奇的性質
反向弧的作用以及代碼邊中的c
下文默認是找增廣路，不管是用什么算法，反正就是找增廣路。
有人可能會問，為什么反向弧這條邊不存在于原圖當中，為什么能夠在增廣路徑的時候走過它？
先思考反向弧在殘余網絡中有意義的原因？
是因為原弧曾經存在于增廣路徑中。
其實反向弧的存在，就是提供了一次后悔操作。
在下圖中：
（紅邊表示正在找增廣的邊）
我們發現，(B)堵住了，其原因是因為((A,C))沒有走((C,D))，別跟我說什么長度最小，隨便改一下照樣卡，那么我們就設置反向邊，叫做后悔，至于其意義，后面具體講，至少我們發現設置反向邊后，((A,B))就可以走((B,C))直接到(D)了。
其意義現在講，對于路徑(p1)：(st?x→y?ed)，對于路徑(p2)：(st?y→x?ed)，那么其實質上就是走了兩條路徑：(st?x?ed,st?y?ed)。
即：
這就是反向邊的真正含義，在對應到(f)上面，對于((i,j)∈E)，如果本次流過((j,i))流了(k)（很明顯(k≤f(i,j))，因為(f(i,j)≥0)），那么其意義上就是((i,j))之前有(k)的流量取消了（上圖中(x->y)），所以在(f(j,i)+=k,f(i,j)-=k)。
現在聊聊代碼實現中的邊的(c)代表什么。
對應在代碼中的實現，邊的(c)表示殘余流量（下文用(c')表示，其實就是殘余網絡中邊的標號），即(c(i,j)-f(i,j))，就是(c'(i,j))（不難發現在代碼中(c')嚴格(≥0)，滿足上面的對于(c,f)的約束），對應一下就是(c'(j,i)-=k,c'(i,j)+=k)。
而對于((i,j))流過的流量也是同樣如此，同樣是(c'(i,j)-=k,c'(j,i)+=k)。
因此，對于代碼中的(c')的處理，是完美的符合其應該代表的含義的。
合法的f對應流
如果(f)合法，是不是絕對對應著一種流呢？
發現圖中只有(st)的入邊(f=0)，出邊(f≥0)，出邊反之，定義一種網絡中只包含(f>0)且屬于(E)的邊，這個網絡中邊的容量為(f)，每次拿(1)流量去從(st)跑到(ed)，最終一定會找到(sumlimits_{(st,i)∈E}f(st,i))條路徑（到達一個點的流量和這個點流出的流量相等）。
當然，圖中可能還會剩一些環。
需要注意的是，即使你用的是Dinic，也一樣可能存在環，舉一個例子：
st有入邊，ed有出邊
不難發現，(ed)的出邊(100)%不會被經過，(st)的入邊也不可能被經過（除非增廣路走環），因此不用去提前處理使得(st)沒有入邊，(ed)沒有出邊。（除非你用的是其他算法）
雙向邊的兩種處理方法
上文也講了，其實如果原圖中就存在雙向邊有兩種處理方法：
新建一個點，把一條邊變成鏈，即上文做法。
如果你足夠理解反向弧的話，你就會明白，其實反向邊可以直接放在一起，如果對于(c(i,j)=3,c(j,i)=5)，那么你就按其說的在圖中如此設定，這樣是完全沒有問題的。
針對(c(i,j)=3,c(j,i)=5)，我們說明一下，幫助理解。
首先，對于這兩邊只會走一條，兩條都走可以交換執行反向邊操作，因此，(f(i,j)≤0)或者(f(j,i)≤0)是成立的，這樣子的話，如果(f(i,j)>0)表示原圖中只走((i,j))，反之亦然。
非常SB的方法，當兩條邊處理，各自建立反向弧，證明方法同2，100%不推薦，除非你有很大的怨念。
s＜f優化
為什么代碼中(s<f)就(h[x]=0)呢？（相當于認為這個點不能走）
難道其不能再做貢獻了嗎？
事實上是非常肯定的，為了更加直觀的理解，我們定義合法網絡：
如果對于一條邊((x,y))，(h[x]=h[y]-1)，那么這條邊就在合法網絡中。
單純為了直觀理解，其實也沒必要
可以發現，邊和反向邊一定不會同時在合法網絡，所以，只有在合法網絡中的弧流量才會增加，且絕對不會減少。
因此，(x)到(ed)的路徑的集合為(P)，這些路徑上的邊流量只會增加，不會減少，所以這些路徑不可能在本次分層圖(DFS)中再度成為增廣路，所以(x)以后都不用再找了。
當然，如果你不加這個優化，可以被分分鐘卡掉，如下圖：
反向邊本次無用性
其實從上面大家都看出來了，由于合法網絡中弧和反向弧不可能同時出現，所以在這次(DFS)中，反向弧的流量在減少，但是并不會對(DFS)產生貢獻，所以本次(DFS)中，你可以先不給反向弧添加流量，放外面添加。
好像并沒個卵用
Dinic深度嚴格單調遞增性
定理：Dinic中(h[ed])嚴格單調遞增。
反證法：
本次我們建完了分層圖，跑完了流量，這個時候，下一次分層圖的(h[ed])是一樣的！！！這意味著原本存在一條長度為(h[ed])的增廣路徑但是我們沒跑到！！！！
什么辣雞東西？？？
假設最終增廣了(k)條增廣路，因此長度之和為：(k*h[ed])。
其走了本次增廣的反向邊，因此不能在原有的分層圖上增廣，假設(p1)走了(p2)的反向邊，這個時候，你就會驚奇的發現，用反向邊的真實含義，把(p1,p2)調換一下，得到了(p1',p2')，(p1',p2')的長度之和為(p1,p2)的長度之和(-2)，然后不斷執行反向邊的真實含義，最終導致(k)條增廣路徑的長度和小于(k*h[ed])，那么一定存在一條路徑長度小于(h[ed])，違反了(EK)的那個啥推論。
都沒有走反向邊，對于路徑(p)，其一定在合法網絡中。
反證法：
設(d[x])為路徑(p)上(x)到(st)的距離，且(x)在路徑(p)上，如果(h[x]<d[x])，則一定存在一條增廣路徑小于(h[ed])，如果(h[x]>d[x])，怎么可能？所以一定在合法網絡上，所以應該本次就增廣了。
從起點跑和從終點跑
好了，開始講一個完全沒有多大用處的優化：從終點開始建分層圖會快一點。
從根本上講，這種優化是針對于DFS找不到增廣路徑的搜索而言的，實際效果表現不佳很大一部分因為大數據下表現不佳以及BFS本身對于不同的搜索順序也會有一定的效率影響，在這里提出只是單純的因為這個優化對于DFS確實是正優化。（同時幫助理解網上說的從(ed)建圖更加快的理論）
從(st)跑有個非常SB的事情，就是但凡從一個點延伸出來一條鏈，都很容易跑到這條鏈里面去。
但是就有人發現了，從終點開始跑可以避免此情況，這不是吹的，這是有科學的依據的。
首先，增廣路一定是(ed)到(st)的一條路徑，從(st)到(ed)的深度單調遞減且固定減一。
因此，要么這條邊一定在(st)到(ed)的一條最短路徑上，就會被(DFS)（從起點開始跑同樣會走這條邊），否則其的深度絕對不會是單調遞增的，因此(st)不會去訪問他（但是從起點開始跑是可能會去訪問的），所以你會發現，從終點開始跑可以在(DFS)中減掉一些沒有必要的狀態。
反向邊處理方法
對于反向邊，代碼中采用的是(.other)，但是有個更加簡單粗暴的方法，一開始設定(len=1)，這樣建邊就是(2,3)，(4,5)這樣的編號，而這些編號亦或(1)就可以互相轉換了。
當前弧優化
可以發現，一次(DFS)，在一個點(x)在跑((x,y))的邊的時候，會出現兩種情況，(a[k].c<(f-s))，這個時候，(x)會給(y)等于(a[k].c)的流量，如果到達終點的流量不足(a[k].c)，那么(y)無法訪問，這條邊作廢，如果到達了(a[k].c)的流量，這條邊滿流，作廢。
((f-s)≤a[k].c)時，會給這條邊(f-s)的流量，如果跑滿了，說明這條邊尚有余溫存在，下次還可以給，如果沒有，則(y)無法到達，照樣作廢。
觀察上文，其實就是如果跑完這條邊之后，(s<f)，這條邊就作廢，所以可以設置(cur)數組，直接跳過廢掉的邊，并進行搜索（至于初始化可以在(BFS)的時候初始化，或者直接用memcpy把(last)賦給(cur)）。
當然，你可能會問，(f-s=a[k].c)時，跑滿了不照樣爆廢？反正下次訪問也可以(O(1))重置。
LL find(int x,LL f)
{
if(x==ed)return f;
LL s=0,t;
for(int k=cur[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]==h[x]-1 && a[k].c>0)
{
s+=(t=find(y,mymin(a[k].c,f-s)));
a[k].c-=t;a[k^1/*.other*/].c+=t;
if(s==f)return f;//滿足就退出，這步也很重要
}
cur[x]=k;//這條邊沒有全部跑滿，直接溜走
}
if(s<f)h[x]=0;
return s;
}
完整代碼：
#include<cstdio>
#include<cstring>
#define N 310
#define M 11000
using namespace std;
typedef long long LL;
struct node
{
int y,next;
LL c;
}a[M];int last[N],n,m,len=1/*用異或代替.other*/,st,ed;
int cur[N];//當前弧
inline void ins(int x,int y,LL c)
{
len++;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;
len++;a[len].y=x;a[len].c=0;a[len].next=last[y];last[y]=len;
}
int h[N],list[N],head=1,tail=n;
inline bool bt_()
{
memset(h,0,sizeof(h));h[ed]=1;
head=1;tail=2;list[1]=ed;
while(head!=tail)
{
int x=list[head++];cur[x]=last[x];/*只對能走到的點記錄當前弧*/
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(a[k^1].c>0 && h[y]==0)
{
list[tail++]=y;
h[y]=h[x]+1;
}
}
}
return h[st];
}
template<class T>
inline T mymin(T x,T y){return x<y?x:y;}
LL find(int x,LL f)
{
if(x==ed)return f;
LL s=0,t;
for(int k=cur[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]==h[x]-1 && a[k].c>0)
{
s+=(t=find(y,mymin(a[k].c,f-s)));
a[k].c-=t;a[k^1/*.other*/].c+=t;
if(s==f)return f;//滿足就退出，這步也很重要
}
cur[x]=k;//這條邊沒有全部跑滿，直接溜走
}
if(s<f)h[x]=0;
return s;
}
int main()
{
LL ans=0;
scanf("%d%d%d%d",&n,&m,&st,&ed);
for(int i=1;i<=m;i++)
{
int x,y;
LL c;
scanf("%d%d%lld",&x,&y,&c);
ins(x,y,c);
}
while(bt_()==true)ans+=find(st,LL(9999999999999));
printf("%lld
",ans);
return 0;
}
當然，也有人的當前弧是這樣寫的：
template<class T>
inline T mymin(T x,T y){return x<y?x:y;}
LL find(int x,LL f)
{
if(x==ed)return f;
LL s=0,t;
for(int &k=cur[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]==h[x]-1 && a[k].c>0)
{
s+=(t=find(y,mymin(a[k].c,f-s)));
a[k].c-=t;a[k^1/*.other*/].c+=t;
if(s==f)return f;//滿足就退出，這步也很重要
}
}
if(s<f)h[x]=0;
return s;
}
我不是很喜歡這樣寫，因為這可能會破壞(Dinic)中(h[ed])單調遞增的性質，導致分層圖做的比較多（事實上確實會）。
好了，重新分析一波(Dinic)的時間復雜度吧。
(EK,Dinic)慢在了找增廣的時間。
原本沒有當前弧優化的時候，每個點(x)如果一個流量都沒有，那么其不可以到達，所以討論有流量的情況，有流量最壞情況下可能需要把(x)的邊全部遍歷一遍，這意味一條路徑可能還需要(O(m))去找，只不過常數較小（這也是為什么(Dinic)實際表現非常優秀的原因），但是呢，加了當前弧優化（我的寫法），點(x)每條邊要么有流量，要么被廢除，算上廢除邊的時間復雜度：(O(m))，沒經過一條邊就會有一條增廣路，所以一條增廣路的花費是(O(n))的，所以是(O(n^2m))。當然，至于大眾寫法，我不會分析QMQ。
放上一張評測圖吧：
事實上，如果你能想到有什么方法可以使得一條邊經過完之后絕對廢除，且不會影響(h[ed])單調遞增的性質，你就自創了(O(nm))的算法，當然，這很難。現在雖然已經有nm算法，但是太難懂了
參考資料
EK時間復雜度的分析
一篇寫得不錯得最大流博客，術語很齊全
論如何卡掉Dinic(我沒看懂)
咕咕討論，Zadeh Construction是個什么東西
二分圖匹配Dinic重拳出擊
各種算法的時間復雜度以及HLPP的講解
Dinic之神
最大流的正確性
各種算法的時間復雜度
算法導論爺Orz
坑
學習HLPP。（感覺這輩子都看不懂時間復雜度得證明）
卡掉Dinic。誤
證明二分圖中Dinic的時間復雜度。
EK時間復雜度證明中提到的例子。
總結
以上是生活随笔為你收集整理的网络流重制版：最大流Dinic，以及EK、Dinic时间复杂度的证明（含坑）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： dwcs6连接不上access数据库_d
- 下一篇： workman php教程_worker