目录
- 最大流问题介绍
- 图定义
- 源点与汇点
- 最大流问题描述
- Ford-Fulkerson方法
- 回退边与增广图
- 伪代码
- 图解
- Edmonds-Karp算法
- 复杂度
- 代码实现细节
- 代码
最大流问题介绍
图定义
给定一张有向图,a->b
边的权值表示当前情况下,从a到b能够发送的流量上限是多少,比如 a->b = 10
表示当前能够从a发10流量给b,当然我们也可以选择不发那么多。
例子:
假设a->b
之间未有任何流量的发送,此时我们发8流量,那么 a->b = 10 变为 a->b = 2
,a->b
能够发送的流量上限由10 变为 2
源点与汇点
源点只发不收,汇点只收不发,其他点作为中转站,既可以发也可以收,这像极了快递物流网络。。。
源点:卖家
汇点:买家
其他点:快递物流站点
最大流问题描述
从源点能够想方设法发送到汇点的最大流量的值,而求解这个问题就是求解这个最大值
你可能会想:这不是直接把源点发送的流量拉满就行了?????
然而事实是这样的:两点之间发送流量最大值取决于两点之间管道最细的地方的大小(木桶原理),前面塞太多后面放不下。。。
Ford-Fulkerson方法
Ford-Fulkerson不是算法,是一种方法,而通过bfs实现这种方法,叫做Edmonds-Karp算法
回退边与增广图
Ford-Fulkerson定义了一个非常具有创造性的“回退边”
如果我们在a->b
中塞入x流量,表示我们买了x货物,于是我们可以退货。
回退边描述了这种退货的行为,回退边的权值是我们已经塞入的流量的大小(联系现实生活中,买了x货物,最多退货量为x)
我们在原图g的基础上增加回退边,构成原图的增广图ga,增广图包含的回退边的权值等于已经塞入的流量的大小
伪代码
Ford-Fulkerson方法提供了一种求解最大流的思路,是一个很巧妙的贪心思路,这是他的伪代码:
sum = 0
while True:
构造原图g的增广图ga
在增广图ga上找到一条从源点到汇点的最短路径p,这个最短指的是经过的点最少而不是经过的边权值之和最小
if 找不到p :
break
记录p一路走来遇到的"最细"的管道大小f(即经过的所有边中权值的最小值)
通过f来更新原图中路径p上的边:
for 边(a->b) in p:
(a->b)能够通过的流量上限 -= f
(b->a)能够通过的流量上限 += f
sum += f
sum就是图最大流
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
很抽象
图解
Edmonds-Karp算法
EK算法之所以是算法,在于它确定了在增广图上找最短路径的方法,即BFS,因为bfs的特性,b到终点一定是最短路
复杂度
bfs用邻接表,复杂度为O(e),更新边复杂度O(e),而每次最少增长1的流量,假设图最大流答案是f
,则最多需要f
次bfs
,所以总复杂度为(O(e)+O(e) * f) = O(ef)
代码实现细节
- 因为边具有属性,邻接表
adj[x]
不再存储下一个顶点的信息,而是存储所有从x出发的边,在边集合中的下标 - 一条边具有两个属性:起点,当前允许的最大流量
- 因为回退边的存在,总共边的数量是原图边数量的两倍
- 在bfs的同时记录路径使用生成树
father[]
数组即可做到,father[x]=-1
表示x未被访问 - bfs的同时记录最细流量,使用
min_flow[]
数组,假设有边a->b
,那么有min_flow[b] = min(该边允许的流量最大值, min_flow[a])
- bfs返回值为true表示找到,否则没找到路径
- 边的权值为0则不可走,因为每次最小压入1流量
- bfs的时候,正向边或回退边都可以走,只要权值不为0
代码
ps:如果您在着手实现深圳大学算法课程的实验,请手下留情,不要全部copy,否则代码查重系统将会展现他那残忍无情的精准
#include <bits/stdc++.h>
using namespace std;
typedef struct edge
{
int st, ed, val; // 起点, 终点, 还能通过多少流量(其中起点不必要,只是方便打印调试信息)
edge(){}
edge(int a, int b, int c){st=a;ed=b;val=c;}
}edge;
int n,e,src,dst,ans; // 顶点数, 初始边数, 源, 目, 答案
vector<vector<int>> adj; // adj[x][i]表示从x出发的第i条边在边集合中的下标
vector<edge> edges; // 边集合
vector<int> min_flow; // min_flow[x]表示从起点到x的路径中最细流
vector<int> father; // 生成树
bool bfs_augment()
{
for(int i=0; i<n; i++) father[i]=-1;
for(int i=0; i<n; i++) min_flow[i]=1145141919; // inf
father[src] = src;
queue<int> q; q.push(src);
while(!q.empty())
{
int x=q.front(),y; q.pop();
if(x==dst) return true;
for(int i=0; i<adj[x].size(); i++)
{
edge e = edges[adj[x][i]];
y = e.ed;
if(father[y]!=-1 || e.val==0) continue;
father[y] = x;
min_flow[y] = min(e.val, min_flow[x]);
q.push(y);
}
}
return false;
}
void graph_update()
{
int x, y=dst, flow=min_flow[dst], i;
cout<<"更新流量: "<<flow<<" 路径: ";
ans += flow;
vector<int> path;
while(y!=src) // 沿着生成树找起点并沿途更新边
{
path.push_back(y);
x = father[y];
for(i=0; i<adj[x].size(); i++) if(edges[adj[x][i]].ed==y) break;
edges[adj[x][i]].val -= flow;
for(i=0; i<adj[y].size(); i++) if(edges[adj[y][i]].ed==x) break;
edges[adj[y][i]].val += flow;
y = x;
}
path.push_back(y);
for(int i=path.size()-1; i>=0; i--) cout<<path[i]<<" "; cout<<endl;
}
int main()
{
cin>>n>>e>>src>>dst;
adj.resize(n);
father.resize(n);
min_flow.resize(n);
edges.resize(e*2);
for(int i=0; i<e; i++)
{
int st, ed, limit; cin>>st>>ed>>limit;
edges[2*i] = edge(st, ed, limit);
edges[2*i+1] = edge(ed, st, 0);
adj[st].push_back(2*i); adj[ed].push_back(2*i+1);
}
while(1)
{
if(!bfs_augment()) break;
graph_update();
// for(int i=0; i<(); i++) cout<<edges[i].st<<" -> "<<edges[i].ed<<" val="<<edges[i].val<<endl;
}
cout<<"最大流:"<<ans<<endl;
return 0;
}
/*
6 7 0 5
0 2 2
0 1 2
1 4 1
2 4 5
2 3 2
3 5 1
4 5 2
7 11 0 6
0 1 3
0 3 3
1 2 4
2 0 3
2 3 1
2 4 2
3 4 2
3 5 6
4 1 1
4 6 1
5 6 9
*/
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111