网络流专题（最大流与费用流）（一）
生活随笔
收集整理的這篇文章主要介紹了
网络流专题（最大流与费用流）（一）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
流量網絡
? 想要將一些水從S運到T，必須經過一些水站，鏈接水站的是管道，每條管道都有它的最大能容納的水量，求最多S到T能流多少流量。
基本概念
? 這是一個典型的網絡流模型。我們先了解網絡流的有關定義和概念。
? 若有向圖G=(V,E)滿足下列條件：
? 則稱之為網絡流圖，記為G = (V, E, C)
1 .水流不遞增
2 .不能存水
3 流入多少水流出多少水
可改進路（增廣路）
殘留網絡
割切
找一個方法，把S和T斷開，所切截面為流量
所能通過的水流為截面，
所以最大流等于最小割
流量算法的基本理論
? 定理1：對于已知的網絡流圖，設任意一可行流為f，任意一割切為(U, W)，必有：V(f) ≤ C(U, W)。
? 定理2：可行流f是最大流的充分必要條件是：f的殘量網絡中不存在可改進路。
? 定理3：整流定理——
如果網絡中所有的弧的容量是整數，則存在整數值的最大流。
? 定理4：最大流最小割定理——
最大流等于最小割，即max V(f) = min C(U, W)。
方法：
Ford-Fulkson方法
FF方法
Edmond-Karp算法
? EK算法是FF方法中最簡單的一個，當然效率也就比較低
? EK算法的流程與ff方法完全相同，只是在尋找增廣路的時候使用了BFS
? 時間復雜度O（n*m^2）
? 空間復雜度O（n^2）（鄰接矩陣）
? 注意要退流哦！！！！
復雜度太高基本不用
代碼：
#include<bits/stdc++.h> using namespace std; const int maxn=205; const int inf=0x7fffffff; int r[maxn][maxn]; //殘留網絡，初始化為原圖 bool visit[maxn]; int pre[maxn]; int m,n; bool bfs(int s,int t) //尋找一條從s到t的增廣路，若找到返回true {int p;queue<int > q;memset(pre,-1,sizeof(pre));memset(visit,false,sizeof(visit));pre[s]=s;visit[s]=true;q.push(s);while(!q.empty()){p=q.front();q.pop();for(int i=1;i<=n;i++){if(r[p][i]>0&&!visit[i]){pre[i]=p;visit[i]=true;if(i==t) return true;q.push(i);}}}return false; } int EdmondsKarp(int s,int t) {int flow=0,d,i;while(bfs(s,t)){d=inf;for(i=t;i!=s;i=pre[i])d=d<r[pre[i]][i]? d:r[pre[i]][i];for(i=t;i!=s;i=pre[i]){r[pre[i]][i]-=d;r[i][pre[i]]+=d;}flow+=d;}return flow; }int main() {while(scanf("%d%d",&m,&n)!=EOF){int u,v,w;memset(r,0,sizeof(r));///for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&w);r[u][v]+=w;}printf("%d\n",EdmondsKarp(1,n));}return 0; }Sap算法
? sap算法是采用了距離標號的方法求最短增廣路， 而距離標號的思想來自于push__relable（壓入重標記）類算法
? 有興趣的同學可以去了解一下push__relable類算法
Dinic算法
? Dinic算法是一個基于“層次圖”的時間效率優先的最大流算法。
? 層次圖是什么東西呢？層次，其實就是從源點走到那個點的最短路徑長度。
? 于是乎，我們得到一個定理：從源點開始，在層次圖中沿著邊不管怎么走，經過的路徑一定
是終點在剩余圖中的最短路。
? Dinic算法也有類似于sap的為頂點定標的過程——通常用BFS實現……
? 每次從源點開始遍歷，如果一次bfs可以從源點到匯點整個網絡都會變成一個層次網絡
? 在一個分層網絡中， 只有a[i] = = a[j] or a[i] = = a[j] -1時<i，j>才有邊存在。
? 當且僅當a[i] == a[j] -1時，兩點之間的邊才被稱為有用邊，在接下來的尋找增廣路的過程中只會走這樣的有用邊。
? 因此，dfs的時候只要遍歷到匯點即可因為同一層和下一層都更新不了匯點了
完整代碼：
#include <bits/stdc++.h> using namespace std; const long long inf=2005020600; int n,m,s,t,u,v; long long w,ans,dis[520010]; int tot=1,now[520010],head[520010]; struct node {int to,net;long long val; } e[520010];inline void add(int u,int v,long long w) {e[++tot].to=v;e[tot].val=w;e[tot].net=head[u];head[u]=tot;e[++tot].to=u;e[tot].val=0;e[tot].net=head[v];head[v]=tot; }inline int bfs() { //在慘量網絡中構造分層圖 for(register int i=1;i<=n;i++) dis[i]=inf;queue<int> q;q.push(s);dis[s]=0;now[s]=head[s];while(!q.empty()) {int x=q.front();q.pop();for(register int i=head[x];i;i=e[i].net) {int v=e[i].to;if(e[i].val>0&&dis[v]==inf) {q.push(v);now[v]=head[v];dis[v]=dis[x]+1;if(v==t) return 1;}}}return 0; }inline int dfs(int x,long long sum) { //sum是整條增廣路對最大流的貢獻if(x==t) return sum;long long k,res=0; //k是當前最小的剩余容量 for(register int i=now[x];i&∑i=e[i].net) {now[x]=i; //當前弧優化 int v=e[i].to;if(e[i].val>0&&(dis[v]==dis[x]+1)) {k=dfs(v,min(sum,e[i].val));if(k==0) dis[v]=inf; //剪枝，去掉增廣完畢的點 e[i].val-=k;e[i^1].val+=k;res+=k; //res表示經過該點的所有流量和（相當于流出的總量） sum-=k; //sum表示經過該點的剩余流量 }}return res; }int main() {scanf("%d%d%d%d",&n,&m,&s,&t);for(register int i=1;i<=m;i++) {scanf("%d%d%lld",&u,&v,&w);add(u,v,w);}while(bfs()) {ans+=dfs(s,inf); //流量守恒（流入=流出） }printf("%lld",ans);return 0; } //dinic時間復雜度:O(n^2 m).最小費用最大流
? 帶有費用的網絡流圖： G=（V，E，C，W） V：頂點； E：弧；C：弧的容量；W：單位流量費用。
在保證s到t流量最大的前提下，所需的費用最小，這就是最小費用最大流問題．
基本思路：
把弧<i,j>的單位費用w[i,j]看作弧<i,j>的路徑長度，每次找從源點s到匯點t長度最短（費用最小）的可增廣路徑進行增廣。
? 其實就是把ek算法中的廣搜改成spfa……（因為存在負權邊所以得用spfa）
代碼：
bool spfa(int s,int t) {queue<int>q;for(int i=0;i<N;i++){dis[i]=INF;vis[i]=0;pre[i]=-1;}dis[s]=0;vis[s]=1;q.push(s);while(!q.empty()){int u=q.front();q.pop();vis[u]=1;for(int i=head[u];i;i=edge[i].next){int v=edge[i].to;if(edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost){dis[v]=dis[u]+edge[i].cost;pre[v]=i;if(!vis[v]){vis[v]=1;q.push(v);}}}}if(pre[t]==-1)return 0;return 1; } int minCostMaxflow(int s,int t,int &cost) {int flow=0;cost=0;while(spfa(s,t)){int Min=INF;for(int i=pre[t];i;i=pre[edge[i^1].to]){if(Min>edge[i].cap-edge[i].flow)Min=edge[i].cap-edge[i].flow;}for(int i=pre[t];i;i=pre[edge[i^1].to]){edge[i].flow+=Min;edge[i^1].flow-=Min;cost+=edge[i].cost;edge[i^1].flow+=edge[i].cost;edge[i].cost-=edge[i].cost;}flow+=Min;}return flow; } //返回的最大流，cost存的是最小費用洛谷模板題
代碼：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #define ll long long #define inf 50000000 #define re register using namespace std; struct po {int from,to,dis,nxt,w; }edge[250001]; int head[250001],cur[1000001],dep[60001],n,m,s,t,u,num=-1,x,y,l,tot,sum,k,fa[10001]; int dis[5001],vis[5001],xb[5001],flow[5001]; inline int read() {int x=0,c=1;char ch=' ';while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();while(ch=='-')c*=-1,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();return x*c; } inline void add_edge(int from,int to,int w,int dis) {edge[++num].nxt=head[from];edge[num].from=from;edge[num].to=to;edge[num].w=w;edge[num].dis=dis;head[from]=num; } inline void add(int from,int to,int w,int dis) {add_edge(from,to,w,dis);add_edge(to,from,0,-dis); } inline bool spfa() {memset(dis,100,sizeof(dis));memset(vis,0,sizeof(vis));queue<int> q;while(!q.empty())q.pop();for(re int i=1;i<=n;i++){fa[i]=-1;}vis[s]=1;dis[s]=0;fa[s]=0;flow[s]=inf;q.push(s);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(re int i=head[u];i!=-1;i=edge[i].nxt){int v=edge[i].to;if(edge[i].w>0&&dis[v]>dis[u]+edge[i].dis){dis[v]=dis[u]+edge[i].dis;fa[v]=u;xb[v]=i;flow[v]=min(flow[u],edge[i].w);if(!vis[v]){vis[v]=1,q.push(v);}}}}return dis[t]<inf; } inline void max_flow() {while(spfa()){int k=t;while(k!=s){edge[xb[k]].w-=flow[t];edge[xb[k]^1].w+=flow[t];k=fa[k];}tot+=flow[t];sum+=flow[t]*dis[t];} } int main() {memset(head,-1,sizeof(head));int d;n=read();m=read();s=read();t=read();for(re int i=1;i<=m;i++){x=read();y=read();l=read();d=read();add(x,y,l,d);}max_flow();cout<<tot<<" "<<sum; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎總結
以上是生活随笔為你收集整理的网络流专题（最大流与费用流）（一）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 口腔炎症是怎么引起的
- 下一篇： 计算几何基础-1