網絡流初步

概念介紹

網絡流不同之處在于它的本質圖論，但是把圖論的某些概念換了一個說法而已，初步只要了解網絡流的各個概念就可以明白的很快。

下述概念是本人自己定義的，對于網絡流的題目做的還不多，后續會更正。

首先需要理解：網絡流其實是在一個有向圖中，從某個原點開始放水，水沿著管道最后流向匯點的過程，基于此就可以很好的理解一些概念和定理，而不需要十分嚴謹的證明（因為證明意義不大

流網絡： 對于一個 $G(V,E)$ 的單向圖，我們稱為流網絡

容量C： 點和點之間的邊權成為容量

流量F： 通俗點說，點與點之間流過的水流量，和物理定義流量一致。一個很顯然的性質：$F\le C$ 即流量不能超過容量

原點和匯點： 水流出的點，和水流入的點。

可行流： 全稱可以流進去的流量，$F(u,v)$ 表示從 u 點流到 v 點的流量

流網絡的可行流：即從原點或者匯點流入或者流出的總流量 $|F|$

最大流： 全稱最大可行流，比較抽象，實際意義就是：從原點可以流出的最大流量，或者是匯集到匯點的最大流量。

殘留網絡： 對于一個每條邊都確定流量F的流網絡，如果存在某條邊 $C?F>0$ ，即如果可以的話，還可以從 $u\to v$ 流動 $C?F$ 的水，那么我們將這些差值重新構造一張圖，形成的網絡被稱為殘留網絡，十分形象，同時還會建立反向邊，不過權值變成 $?F$ ，可以理解為水反向流動。此時構成完整的殘存網絡。

增廣路： 在殘存網絡中，存在一條路徑使得從S到T，該條路徑流過的水>0，也就是路徑最小值大于零，則稱為該條路徑成為增廣路。

割：對于原點S 和 匯點T，我們通過劃分將點集分成兩部分，滿足 S點集中點可以從S到達，T點集中點可以到達T，但是T和S不能在一個集合，此時我們成為是流網絡中的一個割。

割的容量： 即連接點集 S 和點集 T 的邊權的容量

割的流量： 同上，邊權的流量

最小割： 全稱最小割的容量。

結論

• 如果殘留網絡不存在增廣路，此時流網絡的可行流最大，即最大流

  證明： 主觀十分好理解：如果不存在一種路徑使得水從原點流到匯點，那么此時說明不能再流動，那么此時就是最大流量

  證明充要：也很顯然，既然是最大流量，那么就不可能存在讓自己流量在增加的路

• 如果殘留網絡不存在增廣路，那么一定存在一種割的兩個點集 $S,T$，滿足 $|F|={\sum }_{u\in S,v\in T}c(u,v)$

  證明：現在畫圖更好理解這句話的意思：
  

  公式含義就是粉色框的邊權的容量要等于流網絡的可行流。 y總的證明:

  我們這樣構造 S點集：在殘留網絡$G_f$ 中所有從S點出發邊權容量不是 0 的點，剩余點歸算于T點，那么對于這割的容量就是0，可以發現，這樣的集合是可以構造出來的，因為有這個$G_f$ 不存在增廣路的條件，那么所有的路徑至少存在一個邊權容量為0。

  那么因為每個割的殘留網絡容量為0，那么說明每條邊都是某條流過的路徑的最小值（或者是某些最小值的和，因為可能會存在距離S更近的某條邊殘余容量為0，這些流量之后恰好分開流向后面的最小值們，本質上是還是所有流過的路徑最小值的貢獻總和，可以理解為是所有的最小值邊成為了割），也就是該條路徑的流量，那么將這些流量加起來就是總流量。因為從S點流出的流量必須經過割中的所有邊權才能到達T，又因為每個邊的容量等于流量，所以滿足 $|F|=\sum C(u,v)$

• 如果存在兩個點集 $S,T$，滿足 $|F|={\sum }_{u\in S,v\in T}c(u,v)$，那么$|F|$ 一定是最大流

證明：很顯然，因為割的每條邊的流量完全等于容量（由2可知（因為不存在增廣路））,試想，我們將連接兩個點集的之間割的容量全部得到了（S,T 之間可傳遞的最大容量），那么此時的流量和就是最大流。

• 最大流=最小割

  由上面的三個證明便可以得到，最大流 $\to$ 不存在增廣路 $\to$ 最小割 $\to$ 最大流

這是最重要的證明，便于以后的建邊和理解。

最大流

算法實現：

EK算法

算法思想：在圖中不斷找增廣路，然后對邊更改刪掉增光路，對答案造成貢獻，最后不存在增廣路就是答案。時間復雜度：$O(n{m}^2)$，時間復雜度不會證明，不過可以滿足 n<10000 以下的級別

模板:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){int x;scanf("%lld",&x);return x;}
const int B=1e6+10;
int p;
int n,m,S,T;
int head[1010];
int cnt;
struct node
{int u,v,nxt,w;
}e[B<<1];
void modify(int u,int v,int w)
{e[cnt].nxt=head[u];e[cnt].v=v;e[cnt].w=w;head[u]=cnt;cnt++;
} 
void add(int u,int v,int w)
{modify(u,v,w);modify(v,u,0);
}
int d[1010];
int pre[1010];
int vis[1010];
int inf=0x3f3f3f3f;
bool bfs()
{queue<int>q;memset(vis,0,sizeof(vis));q.push(S); vis[S]=1; d[S]=inf; while (!q.empty()){int u=q.front();q.pop();for (int i=head[u];i!=-1;i=e[i].nxt){int v=e[i].v;if (vis[v] || e[i].w==0) continue;d[v]=min(d[u],e[i].w);vis[v]=1;pre[v]=i;if (T==v) return 1;q.push(v);}}return 0;
}
int EK()
{int r=0;while (bfs()){r+=d[T];for (int i=T;i!=S;i=e[pre[i]^1].v){e[pre[i]].w-=d[T];e[pre[i]^1].w+=d[T];}}return r;
}
void work()
{cin>>n>>m>>S>>T;memset(head,-1,sizeof(head));for (int i=1;i<=m;i++){int u=read(),v=read(),c=read();add(u,v,c);}cout<<EK();
}
signed main()
{p=1;while (p--) work();return 0;
}

網絡流細節

雙向建邊的時候需要注意的地方

• cnt從 0 開始，不是1
• for 循環里，邊界 i!=-1 而不是 i!=0

費用流

費用流被稱為：最小費用最大流

每個流量上又添加了一個單位流量花費。要求在最大流的情況下花費最小。

寫法：把bfs找增廣路，改寫成SPFA找增廣路就可以

證明：

最終可以從s點到達T做出貢獻的路徑是一定的，每條路徑之間可能存在平替的現象，Bfs只是從中隨便選擇了幾條，但我們可以將其平替，如下圖

這些路徑中，存在多種方案滿足條件，要想花費最小，直接貪心就可。以前之所沒有想明白，就可這張圖一樣，我想的是如果先把 6 的路徑找出來，最后就只剩下 2 的路徑才能成為8

不過我忘記了，還可以從 4 中走2，并不一定非要走4，所以這就不需要擔心當前選擇影響后續可選擇對象的問題了，因為當前的選擇不影響后續任何選擇，不會導致選擇對象數量發生變化，故可以直接貪心

模板

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){int x;scanf("%lld",&x);return x;}
const int B=1e6+10;
int p;
int n,m,S,T;
int head[B];
int cnt;
struct node
{int u,v,nxt,c,w;
}e[B<<1];
void modify(int u,int v,int c,int w)
{e[cnt].nxt=head[u];e[cnt].v=v;e[cnt].c=c;e[cnt].w=w;head[u]=cnt;cnt++;
} 
void add(int u,int v,int c,int w)
{modify(u,v,c,w);modify(v,u,0,-w);
}
int d[5010];
int pre[5010];
int vis[5010];
int inf=0x3f3f3f3f;
int dis[5010];
bool bfs()
{queue<int>q;for (int i=1;i<=n;i++){vis[i]=0;dis[i]=inf;}q.push(S); vis[S]=1; d[S]=inf; dis[S]=0;while (!q.empty()){int u=q.front();q.pop();vis[u]=0;for (int i=head[u];i!=-1;i=e[i].nxt){int v=e[i].v;if (e[i].c==0) continue;if (dis[v]>dis[u]+e[i].w){dis[v]=dis[u]+e[i].w;pre[v]=i;d[v]=min(d[u],e[i].c);if (!vis[v]){vis[v]=1;q.push(v);}}}}return dis[T]!=inf;
}
void EK()
{int r=0;int sum=0;while (bfs()){r+=d[T];sum+=d[T]*dis[T];for (int i=T;i!=S;i=e[pre[i]^1].v){e[pre[i]].c-=d[T];e[pre[i]^1].c+=d[T];}}printf("%lld %lld", r,sum);
//	cout<<r<<" "<<sum<<"\n";
}
void work()
{cin>>n>>m>>S>>T;for (int i=1;i<=n;i++) head[i]=-1;for (int i=1;i<=m;i++){int u=read(),v=read(),c=read(),w=read();add(u,v,c,w);}EK();
}
signed main()
{p=1;while (p--) work();return 0;
}

r,sum);
// cout<<r<<" “<<sum<<”\n";
}
void work()
{
cin>>n>>m>>S>>T;
for (int i=1;i<=n;i++) head[i]=-1;
for (int i=1;i<=m;i++)
{
int u=read(),v=read(),c=read(),w=read();
add(u,v,c,w);
}
EK();
}
signed main()
{
p=1;
while (p–) work();
return 0;
}