最大流

最大流 - 增广路算法

思想

将A看作水源,G看作汇点,每一条边可以看作管道,每个管道有一个最大容量,每条路上有一个流量。很明显每条管道上的流量是不可能超过管道的容量的。

现在水从A源源不断的流入,那么单位时间内流过G的最大流量是多少?

算法很显然: 不断找能从起点走到汇点的路即可。

接下来介绍增广路算法。

什么是增广路? 就是每一条能从起点走到汇点的路,已经满流的路就不用管了。

证明: 若还能够从s出发,找到一条通往t的,权值不为0的路径,即当前的流量还可以继续增加。直到无法找到这样一条路,这样的流量就是最大的。

为什么要建立反向边?

因为在有的图中 不只有单向边 可能从 a到b 的容量为5, b到a的容量为3.

所以对于只有单向边的图,我们可以认为 反向边的容量为0.

模板

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
struct Edge{
int from,to,cap,flow;
Edge(int u,int v,int c,int f): from(u),to(v),cap(c),flow(f) {}
};
struct EdmonsKarp{ //时间复杂度O(v*E*E)
int n,m;
vector<Edge> edges; //边数的两倍
vector<int> G[maxn]; //邻接表,G[i][j]表示节点i的第j条边在e数组中的序号
int a[maxn]; //起点到i的可改进量
int p[maxn]; //最短路树上p的入弧编号

void init(int n){
for(int i=0;i<=n;i++) G[i].clear();
edges.clear();
}

void AddEdge(int from,int to,int cap){
edges.push_back(Edge(from,to,cap,0));
edges.push_back(Edge(to,from,0,0)); //反向弧
m = edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}

int Maxflow(int s,int t){
int flow = 0;
for(;;){
memset(a,0,sizeof(a));
queue<int> Q;
Q.push(s);
a[s] = INF;
while(!Q.empty()){
int x = Q.front();Q.pop();
for(int i=0;i<G[x].size();i++){
Edge& e = edges[G[x][i]];
if(!a[e.to] && e.cap > e.flow){ //!a[e.to] 是了保证不会回退和出现分叉
p[e.to] = G[x][i]; //记录边的编号
a[e.to] = min(a[x],e.cap - e.flow);
Q.push(e.to);
}
}
if(a[t]) break; //走到汇点
}
if(!a[t]) break; //没有一条增广路存在
for(int u=t;u != s;u = edges[p[u]].from){
edges[p[u]].flow += a[t];
edges[p[u]^1].flow -= a[t];
}
flow += a[t];
}
return flow;
}
};
Thank you for your support!