目录

最大流流算法

（EK算法）

时间复杂度 O(V*（E^2）)

 

Dinic算法

时间复杂度O(（V ^ 2） * E)

---

在洛谷题解中看到了一句很有启发的话：网络流善于解决各种有要求的匹配

联想到题目是匹配问题，且满足网络流要求的数据范围，可以尝试网络流

 

V是点的数目，E是边的数目

最大流流算法

（EK算法）

时间复杂度 O(V*（E^2）)

定义：

我们有一个 源点（只有流出量） 和 汇点（只有流入量）

每条边有一个 流量 和 容量，流量最初为0，容量是题目告知我们的，我们要求的是 在所有边的 流量 <= 容量 && 每个点流入量 = 流出量 时，流入汇点的最大流是多少。

首先我们需要知道残留网络：

残留网络就是反向图的流量，我们正向遍历一个图，会走一条路径到汇点。

一条路径的   增广路 = min（经过的每条边的 {容量 - 当前流量} ）

但是我们这条边可能是反向的流，所以

• 正向边的容量 -= 增广路
• 反向边容量 += 增广路

找到增广路，我们就 flow += 增广路

当找不到增广路就结束了这个算法。

因为看了vector建图和链式前向星建图的效率和空间差异，就手动改了一下模板，不用常用的mp[][] 数组标记，练习一下链式前向星。

洛谷3376

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <algorithm>
#include <set>
#include <vector>
#include <stack>
#define Clear( x , y ) memset( x , y , sizeof(x) );
#define Qcin() std::ios::sync_with_stdio(false);
using namespace std;
typedef long long LL;
const int Maxn = 1e4 + 7;
const int MaxN = 2e5 + 7;
const int Inf = 1e9 + 7;
// O{V * E ^ 2}
/*
源点 st , 汇点 ed
*/
int N , M;
int st , ed;

int cnt;
struct edge{
	int Next;//下一条边的存储下标
	int to;//这条边的终点
	int w;//边权
};
edge Edge[MaxN];
int head[Maxn];//以 i 为起点的第一条边的标记
void AddEdge(int u , int v , int w){
	Edge[++cnt].Next = head[u];
	Edge[cnt].w = w;
	Edge[cnt].to = v;
	head[u] = cnt;
}

int pre[Maxn][2];
int Flow;
int flow[Maxn];
queue <int> que;
bool Bfs(){
	while(!que.empty())	que.pop();
	for(int i = 0 ; i <= N ; i++) pre[i][0] = pre[i][1] = -1;
	flow[st] = Inf;
	int q;
	que.push(st);
	while(!que.empty()){
		q = que.front(); que.pop();
		if(q == ed)	break;
		for(int i = head[q] ; ~i ; i = Edge[i].Next){
			int nq = Edge[i].to;
			if(nq != st && Edge[i].w && pre[nq][0] == -1){//下个点nq不是st,且边权>0,nq没被遍历过
				pre[nq][0] = i;//记录前一条边的编号
				pre[nq][1] = q;//记录nq前一个点q
				flow[nq] = min(Edge[i].w , flow[q]);//到nq路径上取min边权
				que.push(nq);
			}
		}
	}
	if(pre[ed][0] == -1)	return false;
	return true;
}

void MaxFlow(){
	int add , pl , fa , p;
	while(Bfs()){
		add = flow[ed];
		p = ed;
		while(p != st){
			pl = pre[p][0];//p上一条边的编号
			p = pre[p][1];//p变为它的上一个点
			Edge[pl].w -= add;
			Edge[pl^1].w += add;
		}
		Flow += add;
	}
	printf("%d\n",Flow);
	return;
}

void init(){
	for(int i = 0 ; i <= N ; i++)	head[i] = -1;
	cnt = -1;//从-1 开始 可以用 x ^ 1 来关联正反边
	return;
}

int main()
{
	scanf(" %d %d %d %d",&N,&M,&st,&ed);
	init();
	for(int i = 1 ; i <= M ; i++){
		int u , v , c , ct1 , ct2;	scanf(" %d %d %d",&u,&v,&c);
		AddEdge(u , v , c);
		AddEdge(v , u , 0);
	}
	MaxFlow();
	return 0;
}

 

Dinic算法

EK通常解决10^3 –10^4规模的网络 
而dinic能解决10^4–10^5的网络

时间复杂度O(（V ^ 2） * E)

(真的快了不是一点，这一道题，Dinic是EK的 1/4 时间)

算法流程：

• 在存在增广路的边上建立分层图，如果汇点不在存在增广路的分层图上，那么就不存在新的增广路，结束算法
• 当存在汇点增广路，执行Dfs操作，在分层图中寻找增广路，增广路径从 u 到 v ， 当且仅当dep[v] = dep[u] + 1
• 找到增广路，Dfs回溯时减去增广路，一个节点可能减了多次增广路。

洛谷3376

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <algorithm>
#include <set>
#include <vector>
#include <stack>
#define Clear( x , y ) memset( x , y , sizeof(x) );
#define Qcin() std::ios::sync_with_stdio(false);
using namespace std;
typedef long long LL;
const int Maxn = 1e4 + 7;
const int MaxN = 2e5 + 7;
const int Inf = 1e9 + 7;

int N , M;
int st , ed;
int Flow;

int cnt;
struct edge{
	int Next;
	int to;
	int w;
};
edge Edge[MaxN];
int head[Maxn];
void AddEdge(int u , int v , int w){
	Edge[++cnt].Next = head[u];
	Edge[cnt].w = w;
	Edge[cnt].to = v;
	head[u] = cnt;
}

int dep[Maxn];
queue <int> que;
bool Bfs(){
	for(int i = 1 ; i <= N ; ++i)	dep[i] = 0;
	while(!que.empty())	que.pop();
	dep[st] = 1;
	que.push(st);
	int q , v;
	while(!que.empty()){
		q = que.front(); que.pop();
		for(int i = head[q] ; ~i ; i = Edge[i].Next){
			v = Edge[i].to;
			if(Edge[i].w && !dep[v]){
				que.push(v);
				dep[v] = dep[q] + 1;
				if(v == ed)	return true;
			}
		}
	}
	return false;
}

int Dfs(int x , int flow){
	if(x == ed)	return flow;
	int res = flow , add;
	for(int i = head[x] ; ~i && res ; i = Edge[i].Next){
		int v = Edge[i].to;
		if(Edge[i].w && dep[v] == dep[x] + 1){
			add = Dfs(v , min(res , Edge[i].w));
			if(!add)	dep[v] = 0;
			Edge[i].w -= add;
			Edge[i^1].w += add;
			res -= add;
		}
	}
	return flow - res;
}

void Dinic(){
	int flow;
	while(Bfs()){
		while(flow = Dfs(st , Inf)){
			Flow += flow;
		}
	}
	printf("%d\n",Flow);
}
void init(){
	for(int i = 1 ; i <= N ; i++)	head[i] = -1;
	Flow = 0;
	cnt = -1;
}


int main()
{
	scanf(" %d %d %d %d",&N,&M,&st,&ed);
	init();
	for(int i = 1 ; i <= M ; i++){
		int u , v , c; scanf(" %d %d %d",&u,&v,&c);
		AddEdge(u , v , c);
		AddEdge(v , u , 0);
	}
	Dinic();
}

 

洛谷 P2763

---

我们已经学会了基础的最大流，那么就需要继续研究最小费用最大流 和 最大费用最大流

最小费用最大流