前言：
網路流就像自來水廠到你家的水管，自來水廠(源點S)源源不斷的提供水，水通過不同水管匯集于你家(設自來水廠的水全到你家，匯點T)，自來水廠到你家的水管網是一個復雜的有向圖，每一節水管都有一個最大承載流量(容量)，自來水廠不放水，你家就沒水了，但是就算自來水廠拼命地往管網里面注水，你家收到的水流量也是上限，畢竟每根水管承載量有限，這就是一個有向圖，所有的水都從一個點流出（水廠），最后全部匯聚到一個點（你家），
網路
網路(流網路)是指一個有向聯通圖，由一個點集和一個邊集構成 G=(V,E)，
- 圖中每個邊都有一個屬性，稱為容量 c(u,v)，表示最大能夠通過的水量(或其他限制條件)，
- 圖中有兩個特殊點：源點(S)和匯點(T)，源點 S 有無限多的水流可以向外流出，匯點 T 可以接受無限多的水流，
ps:不考慮反向邊，如果有反向邊，通過加點變成沒有反向邊的圖，
\(\;\;\;\) 如果一條邊不存在，則定義這條邊的容量是0，
流
對于一個網路流圖 G=(V,E)，每條邊（u,v）上給定一個實數 f(u,v)，f(u,v) 為 邊(u,v) 上的流量，
對于任何一條有向邊(u,v)，f(u,v)=-f(v,u)
一個可行流f需滿足兩個條件:
-
流量守恒：$$?x\in ( V ? { S,T} )，\sum\limits_{?(v,x)∈E}f(v,x)=\sum\limits_{?(x,v)∈E}f(x,v)$$
除源點和匯點外，流入其余每一個點的流量和等于流出這個點的流量和，不存盤流量，
-
容量限制 0 \(\leq\) f(u,v) \(\leq\) c(u,v)
我們永遠賺不到自己認知以外的錢，水管也永遠裝不下比自己容量還大的水
|f| 表示可行流的流量值，定義為從源點流出的流量或匯點流入的流量.
|f| =\(\sum\limits_{(s,v)?E}\)f(s,v) ? \(\sum\limits_{(v,s)?E}\)f(v,s)
和流網路的關系：一個流網路中有很多個可行流，G\(\begin{cases} f_1\\f_2\\f_3\\\vdots\end{cases}\)
殘留網路
流網路里的每一個可行流f都有自己的殘留網路\(G_f\)，對于不同的可行流，殘留網路不同，
\[G\begin{cases}f_1\Rightarrow G_{f_1}\\f_2\Rightarrow G_{f_2}\\f_3\Rightarrow G_{f_3}\\ \vdots\end{cases} \]殘留網路同樣也是由一個點集和一個邊集構成,\(G_f\)=(\(V_f\),\(E_f\))
- 點集包含原網路所有點(\(V_f\)=V)，
- 邊集包括原網路中所有邊和所有反向邊(\(E_f\)=E \(\bigcup\) E中所有反向邊)，
而殘留網路中，邊的容量c'(u,v)是原網路的殘留容量
c'(u,v)=\(\begin{cases}c(u,v)-f(u,v)\;\; (u,v)\in E ,表示還有多少流量可以用，容量減去流量\\f(v,u) \qquad \;\,\qquad (v,u)\in E ,表示可以退回去多少流量\end{cases}\)
流量計算：|f+f'|=|f|+|f'|
流量相加指的是每條邊對應相加：殘留網路和原網路邊的方向相同，累加；相反，相當于退回的流量，減去；
關于反向邊
反向邊是一個很牛逼的反悔機制，可以把前面流的流量退回去，這樣，就能多去考慮被之前的通路阻斷的情況，不會漏解，換句話說，反向邊的存在讓我們可以在所有的情況里選取最符合我們所需的情況，
\[\\ \]原網路的可行流（f）和殘留網路可行流（f’）有啥關系？
f'+f也是原網路G的另外一個可行流，
證明:
1.流量守恒證明
\(\quad\;\;\because\) f和f'都滿足流量守恒
\(\quad\;\;\therefore ?x\in ( V ? \{S,T\} )\sum\limits_{?(v,x)∈E}f(v,x)+\sum\limits_{?(v,x)∈E}f'(v,x)=\sum\limits_{?(x,v)∈E}f(x,v)+\sum\limits_{?(x,v)∈E}f'(x,v)\)
\(\quad\;\;\therefore\) f+f'滿足流量守恒
2.容量限制證明
- 考慮正向邊，當c'(u,v)=c(u,v)-f(u,v) 時
\(\quad\;\;\because\) 0 \(\leq\) f'(u,v) \(\leq\) c'(u,v)=c(u,v)-f(u,v)
\(\quad\;\;\therefore\) 0 \(\leq\) f'(u,v) \(\leq\) c'(u,v)=c(u,v)-f(u,v)
\(\quad\;\;\therefore\) 0 \(\leq\) f'(u,v) + f(u,v) \(\leq\) c(u,v) 滿足正向邊容量限制
- 考慮反向邊，當c'(u,v)=f(v,u)時
\(\quad\;\;\because\) 0 \(\leq\) f'(u,v) \(\leq\) c'(u,v)=f(v,u) \(\leq\) c(v,u)
\(\quad\;\;\therefore\) 0 \(\leq\) f(v,u) - f'(u,v) \(\leq\) c(u,v)
\(\quad\;\;\therefore\) 0 \(\leq\) f(v,u) + f'(v,u) \(\leq\) c(u,v) 滿足反向邊容量限制
增廣路
殘留網路里，從源點沿著流量 > 0的邊能夠走到匯點，這樣的路徑為增廣路徑，
對于當前流網路里的可行流來說，殘留網路里無增廣路徑，則該可行流為最大流，
最大流
對于一個流網路來說，有很多可行流最大流是最大可行流，
EK演算法
基于FF方法的一種演算法
由最大流的定義得知，當殘留網路里，不存在增廣路時，當前可行流為最大流，那么EK演算法就是把增廣路一條一條的找到，那么不斷地消除這一條條增廣路，從而求得最大流，對增廣路對應的原圖里面的路徑增流，就可以消除這條增廣路，
- 找增廣路
在殘量網路中，任意找一條從 S 到 T 的路徑，邊權均不為 0，則這條路徑是一條增廣路，這里我用的是bfs - 更新殘留網路
在找到一條增廣路后，找出路徑上的邊權最小值 x ，然后把路徑上所有邊權都減去x（也就是找增廣路后，這條路徑上流過 x 的流量）
我們不斷的重復上面兩個操作，直到找不到增廣路為止，則沒有一條路徑可以給匯點增加流量，此時，匯點匯集的流量為最大流，
那么如果一條更優的路徑被前面消除的一條路截斷了怎么辦呢？
這個時候，反向邊的反悔機制，就起到了很牛逼的作用，我直接反悔，把這個之前通過增流消除的增廣路進行退流，把之前增加的流量退回來，對當前更優的增廣路進行消除，就ok了
代碼實作：
點擊查看代碼
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1010,M=20010,inf=1e8;
int e[M],ne[M],f[M];
int q[N],d[N],h[N],pre[N],idx;
int m,n,S,T;
bool st[N];
void add(int a,int b,int c)
{
e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs()
{
int tt=0,hh=0;
memset(st,0,sizeof st);
q[0]=S,st[S]=true,d[S]=inf;
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];~i;i=ne[i])
{
int ver=e[i];
if(!st[ver]&&f[i])
{
st[ver]=true;
d[ver]=min(f[i],d[t]);
pre[ver]=i;
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
inline int EK()
{
int ans=0;
while(bfs())
{
ans+=d[T];
for(int i=T;i!=S;i=e[pre[i]^1])
{
f[pre[i]]-=d[T],f[pre[i]^1]+=d[T];
}
}
return ans;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&S,&T);
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
printf("%d\n",EK());
return 0;
}
Dinic演算法
blablablabla...
點擊查看代碼
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=10100,M=200100,inf=1e8;
int e[M],ne[M],f[M];
int q[N],d[N],h[N],cur[N],idx;
int m,n,S,T;
void add(int a,int b,int c)
{
e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs()
{
int tt=0,hh=0;
memset(d,-1,sizeof d);
q[0]=S,d[S]=0,cur[S]=h[S];
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];~i;i=ne[i])
{
int ver=e[i];
if(d[ver]==-1&&f[i])
{
d[ver]=d[t]+1;
cur[ver]=h[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
inline int find(int u,int limits)
{
if(u==T) return limits;
int flow=0;
for(int i=cur[u];~i&&flow<limits;i=ne[i])
{
int ver=e[i];
cur[u]=i;
if(d[ver]==d[u]+1&&f[i])
{
int t=find(ver,min(f[i],limits-flow));
if(!t) d[ver]=-1;
f[i]-=t;
f[i^1]+=t;
flow+=t;
}
}
return flow;
}
inline int Dinic()
{
int ans=0,flow;
while(bfs())
{
while(flow=find(S,inf)) ans+=flow;
}
return ans;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&S,&T);
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
printf("%d\n",Dinic());
return 0;
}
無源匯上下界可行流
點擊查看代碼
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1010,M=30010,inf=1e8;
int e[M],ne[M],f[M],l[M];
int q[N],d[N],h[N],cur[N],idx,A[N];
int m,n,S,T;
void add(int a,int b,int c,int d)
{
e[idx]=b,f[idx]=d-c,l[idx]=c,ne[idx]=h[a],h[a]=idx++;
e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs()
{
int tt=0,hh=0;
memset(d,-1,sizeof d);
q[0]=S,d[S]=0,cur[S]=h[S];
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];~i;i=ne[i])
{
int ver=e[i];
if(d[ver]==-1&&f[i])
{
d[ver]=d[t]+1;
cur[ver]=h[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
inline int find(int u,int limit)
{
if(u==T) return limit;
int flow=0;
for(int i=cur[u];~i&&flow<limit;i=ne[i])
{
int ver=e[i];
cur[u]=i;
if(d[ver]==d[u]+1&&f[i])
{
int t=find(ver,min(f[i],limit-flow));
if(!t) d[ver]=-1;
f[i]-=t;
f[i^1]+=t;
flow+=t;
}
}
return flow;
}
inline int Dinic()
{
int ans=0,flow;
while(bfs())
{
while(flow=find(S,inf)) ans+=flow;
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
S=0,T=n+1;
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
add(a,b,c,d);
A[a]-=c,A[b]+=c;
}
int tot=0;
for(int i=1;i<=n;i++)
{
if(A[i]>0)
{
add(S,i,0,A[i]);
tot+=A[i];
}
else if(A[i]<0)
{
add(i,T,0,-A[i]);
}
}
if(Dinic()!=tot) puts("NO");
else
{
puts("YES");
for(int i=0;i<2*m;i+=2)
{
printf("%d\n",f[i^1]+l[i]);
}
}
return 0;
}
有時間再寫..
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498634.html
標籤：其他