网络流（一） 最大流问题

大家好，欢迎来到IT知识分享网。

目录

一. 网络流概述

1. 基本概念

2. 名词解释

3. 基本性质

4. 最大流最小割定理

二. 最大流问题

1. 问题描述

2. 求解算法

2.1. 一般增广路算法（EdmondsKarp）

2.2. 分层图 Dinic 算法

2.3 Dinic算法的当前弧优化

一. 网络流概述

1. 基本概念

在一个有向图上选择一个源点，一个汇点，每一条边上都有一个流量上限（以下称为容量），即经过这条边的流量不能超过这个上界，同时，除源点和汇点外，所有点的入流和出流都相等，而源点只有流出的流，汇点只有汇入的流。这样的图叫做网络流。

2. 名词解释

3. 基本性质

        对于任意一个时刻，设f(u,v)为实际流量，c(u,v)为容量，则任意时刻流网络满足三个性质：

（1）容量限制：对于任意u，v，都有f（u,v） <= c（u,v）。即任意时刻流量都不超过容量；

（2）流守恒性：除了源点与汇点之外，其余任意一点，都满足流入该点总量 = 流出该点总量，节点自身不会产生或者消耗流量，只是中转媒介；

（3）反对称性：对于任意的u,v ，一定有f（u,v） = -f（v,u） 。 从u到v流了 l 流量就相当于从v到u流了-l 的流量；

4. 最大流最小割定理

        这里的割定义为边割集中所有边的容量之和，最大流最小割定理如下：

（1）任意一个流都小于任意一个割：任意一个边割集内的边被删掉以后，都会使图不联通，使流断掉；所以任意一个流肯定都小于任意一个割。

（2）构造出的一个流等于一个割；

（3）最大流等于最小割；

二. 最大流问题

1. 问题描述

形象一点的话，假如现在有一个自来水厂要往你家通水，自来水厂到你们家连接了很多水管，并且中途经过很多转接点。每根水管都有粗细，通过管子的水流肯定不能太大，不然会撑爆管子。现在问你，从自来水厂放水最多到你家能汇聚有多少水。这就是网络流的最大流问题。给出你源点与汇点，给你m条有向路和每条路的容量，求最大流。

2. 求解算法

        基于增广路定理：网络达到最大流当且仅当残留网络中没有增广路。因此增广路算法的思想（Ford-Fulkerson）是：沿着图中的一个可行流开始，从源点往汇点不断寻找增广路，每找到一条就处理一次。不断重复寻找直到图中不存在增广路，这就是增广路算法。其算法流程如下：

• 我们找一条从源点可以通向汇点的通路，通路上的最小可行流就是路上所有水管都能承受的流量，我们就可以通上这些水。并且把所有路的流量加上这些，表示该水管已经通了这些水。
• 不断继续寻找下一个可行的增广路，直到图中找不到从源点到汇点的可行路。但是这时不一定是最大流，因为我们刚开始选择很单一。所以我们这里就增加反向弧，从u到v通l 就 从v到u通l。

        为什么增加反向弧呢？这是给流量一个反悔的机会，比如我本来从u到v，但是我发现从u分流一部分到v，另一部分走另一条路时最大，这里就有了反悔的选择。

2.1. 一般增广路算法（EdmondsKarp）

         一般增广路算法由BFS不断寻找增广路，涉及m条边、n个点，其代码时间复杂度为 O（m^2n），但EK算法的算法效率太低。

#include <iostream> #include<bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f const int maxn = 10000 + 7; int head[maxn],n,m,tot,s,t,cost[maxn],pre[maxn];//cost记录到当前点的最小流量，pre记录前导边 struct Edge{ int from,to,next,cap,flow;//cap容量，flow当前流量 }edge[maxn]; void addEdge(int a,int b,int c){ edge[tot].from = a;edge[tot].to = b;edge[tot].next = head[a];edge[tot].cap = c;edge[tot].flow = 0;head[a] = tot++; } int EK(int st,int et){ int maxflow = 0; for(;;){//不断寻找增广路 memset(cost,0,sizeof(cost)); queue<int> que; que.push(st);//从源点开始 cost[st] = INF; while(!que.empty()){ int u = que.front(); que.pop(); for(int i = head[u];~i;i = edge[i].next){ int p = edge[i].to; if(!cost[p]&&edge[i].cap > edge[i].flow){//该点还未被走过 + 该水管残量不为0 cost[p] = min(cost[u],edge[i].cap - edge[i].flow);//取最小 pre[p] = i;//记录前导边 que.push(p); } } if(cost[et])break;//如果到达了终点，结束 } if(!cost[et])break;//如果循环完发现没有到达汇点，说明不存在增广路了达到最大流 for(int i = et;i!=st;i = edge[pre[i]].from){//从汇点往前更新所有边 edge[pre[i]].flow+=cost[et]; edge[pre[i]^1].flow-=cost[et];//反向弧 } maxflow+=cost[et];//更新最大流 } return maxflow; } int main() { int T; scanf("%d",&T); while(T--){ tot = 0; memset(head,-1,sizeof(head)); scanf("%d%d%d%d",&n,&m,&s,&t);//n个点，m条有向边，源点，汇点 for(int i = 0;i<m;i++){ int a,b,v; scanf("%d%d%d",&a,&b,&v); addEdge(a,b,v);//正向建边 addEdge(b,a,0);//反向弧初始容量为0 } int ans = EK(s,t);//求解最大流 printf("%d\n",ans); } return 0; } 

2.2. 分层图 Dinic 算法

        为了解决EK算法的低效过程，我们给每个点标上一个记号来分层，而这个记号就是该点到源点的距离。我们规定每次前进必须走记号比当前点大一的点。这样就保证了每次移动必定前进，是必定距离汇点越来越近的。其流程如下：

（1） 利用 BFS 对原来的图进行分层，即对每个结点进行标号， 这个标号的含义是当前结点距离源点的最短距离(假设每条边的距离都为1)，注意：构建层次图的时候所走的边的残余流量必须大于0

（2）用 DFS 寻找一条从源点到汇点的增广路, 注意: 此处寻找增广路的时候要按照层次图的顺序, 即如果将边(u, v)纳入这条增广路的话必须满足dis[u]=dis[v]−1, 其中 dis[i]为结点 i 的编号。找到一条路后要根据这条增广路径上的所有边的残余流量的最小值l更新所有边的残余流量(即正向弧 – l, 反向弧 + l)。

（3）重复步骤（2）， 当找不到一条增广路的时候, 重复步骤 1, 重新建立层次图, 直到从源点不能到达汇点为止。其代码复杂度为 O（n^2m）。

#include <iostream> #include<bits/stdc++.h> #include<cstdio> #include<cstring> #include<queue> using namespace std; #define INF 0x3f3f3f3f const int maxn = 1000 + 7; typedef long long LL; struct Edge{ int to,next; LL cap,flow; }edge[maxn*20]; int n,m,head[maxn],tot,dist[maxn],s,t; void addEdge(int a,int b,LL c){ edge[tot].to = b;edge[tot].next = head[a];edge[tot].cap = c;edge[tot].flow = 0;head[a] = tot++; edge[tot].to = a;edge[tot].next = head[b];edge[tot].cap = 0;edge[tot].flow = 0;head[b] = tot++; } bool BFS(int st,int et){//BFS分层 queue<int> que; memset(dist,0,sizeof(dist)); que.push(st); dist[st] = 1; while(!que.empty()){ int u = que.front(); que.pop(); for(int i = head[u];~i;i = edge[i].next){ if(!dist[edge[i].to]&&edge[i].cap > edge[i].flow){//没走过这点 + 残量不为0 dist[edge[i].to] = dist[u] + 1; que.push(edge[i].to); } } } if(dist[et]>0)return true;//若汇点有标号说明仍有增广路，否则结束 return false; } LL DFS(int p,LL minFlow){//DFS找增广路 if(p==t||minFlow==0)return minFlow;//到达汇点或者最小分到0了，结束反回 LL flow = 0;//记录从该点分支的所有能走的增广路流量 for(int i = head[p];~i;i = edge[i].next){ if(dist[edge[i].to] == dist[p] + 1&&edge[i].cap > edge[i].flow){//残量不为0 LL f = DFS(edge[i].to,min(edge[i].cap - edge[i].flow,minFlow));//沿这条路走下去的最小增广路流量 edge[i].flow+=f;//更新到当前边 edge[i^1].flow-=f;//反向弧 flow+=f; minFlow-=f;//分流 if(minFlow==0)break; } } return flow; } int Dinic(int st,int et){ if(st==et)return 0; LL maxFlow = 0; while(BFS(st,et)){//不断分层 LL res = DFS(st,INF);//DFS寻找当前分层下所有增广路 maxFlow+=res; } return maxFlow; } int main() { int T; scanf("%d",&T); while(T--){ tot = 0; memset(head,-1,sizeof(head)); scanf("%d%d%d%d",&n,&m,&s,&t); for(int i = 0;i<m;i++){ int a,b; LL val; scanf("%d%d%lld",&a,&b,&val); addEdge(a,b,val); } LL ans = Dinic(s,t); printf("%lld\n",ans); } return 0; } 

2.3 Dinic算法的当前弧优化

        标记每个点遍历到哪条边了，下次遍历这个点的时候直接从这条边开始，避免了又从头开始的弊端。其代码如下：

#include <iostream> #include<bits/stdc++.h> #include<cstdio> #include<cstring> #include<queue> using namespace std; #define INF 0x3f3f3f3f const int maxn = 1000 + 7; typedef long long LL; struct Edge{ int to,next; LL cap,flow; }edge[maxn*20]; int n,m,head[maxn],tot,dist[maxn],s,t,cur[maxn]; void addEdge(int a,int b,LL c){ edge[tot].to = b;edge[tot].next = head[a];edge[tot].cap = c;edge[tot].flow = 0;head[a] = tot++; edge[tot].to = a;edge[tot].next = head[b];edge[tot].cap = 0;edge[tot].flow = 0;head[b] = tot++; } bool BFS(int st,int et){ queue<int> que; memset(dist,0,sizeof(dist)); que.push(st); dist[st] = 1; while(!que.empty()){ int u = que.front(); que.pop(); for(int i = head[u];~i;i = edge[i].next){ if(!dist[edge[i].to]&&edge[i].cap > edge[i].flow){ dist[edge[i].to] = dist[u] + 1; que.push(edge[i].to); } } } if(dist[et]>0)return true; return false; } LL DFS(int p,LL minFlow){ if(p==t||minFlow==0)return minFlow; LL flow = 0; for(int &i = cur[p];~i;i = edge[i].next){//！！注意这里的& ， 使cur[p]跟随i变化，下次dfs到该点直接从上次退出的地方继续开始，不用从头重复了！！！ if(dist[edge[i].to] == dist[p] + 1&&edge[i].cap > edge[i].flow){ LL f = DFS(edge[i].to,min(edge[i].cap - edge[i].flow,minFlow)); edge[i].flow+=f; edge[i^1].flow-=f; flow+=f; minFlow-=f; if(minFlow==0)break; } } return flow; } int Dinic(int st,int et){ if(st==et)return 0; LL maxFlow = 0; while(BFS(st,et)){ for(int i = 1;i<=n;i++)cur[i] = head[i];//初始化标记数组 LL res = DFS(st,INF); maxFlow+=res; } return maxFlow; } int main() { int T; scanf("%d",&T); while(T--){ tot = 0; memset(head,-1,sizeof(head)); scanf("%d%d%d%d",&n,&m,&s,&t); for(int i = 0;i<m;i++){ int a,b; LL val; scanf("%d%d%lld",&a,&b,&val); addEdge(a,b,val); } LL ans = Dinic(s,t); printf("%lld\n",ans); } return 0; }