首页 > 代码库 > 最大流之sap算法

最大流之sap算法

2024-07-02 07:24:26   227人阅读

若有向图G = （V , E）满足下列条件：

1、有且仅有一个顶点S，它的入度为 0 ，这个顶点称为源点。

2、有且仅有一个顶点T，它的出度为 0 ，这个顶点称为汇点。

3、每一条弧都有一个非负数，叫做这条边的容量，边（Vi , Vj）的容量用 Cij 来表示。

则此有向图称为网络流图，记为 G = ( V , E , C) ;

对于网络流图G中，每一条弧( i , j )都给定一个非负数Fij，对于一组数据满足下面三个条件时，称为可行流；

1、对于每条弧都有 Fij < Cij ;

2、出了源点S和汇点T之外，中间任意点流量守恒，即输入流等于输出流；

3、对于源点S和汇点T，从S出去多少就会从T流入多少；

假如有这么一条路，从源点开始，一直一段一段的连到了汇点，并且这条路上的每一段满足Fij < Cij ,则称这条路为增广路；

当找不到增广路时，当前流量就是最大流。

寻找增广路时可以简单地从源点开始做bfs，并不断修改这条路上的最大流。

但事实上并不是这么简单，上面所说的增广路还不是很完整，中间还存在一些细节问题，例如：

我们通过bfs遍历后得到第一条增广路 1 - 2 - 3 - 4 ，然后就不存在增广路径了，其实并不是这样，这个网络流的最大流明显为 2 ，我们可以是使用一个叫反向边的概念来解决这个问题，如图：

这样就解决了增广路算法中的一些细节问题；

 

加入一个网络图中有4个点，5条边组成。如下：

5 4

1 2 40

1 4 20

2 4 20

2 3 30

3 4 10

求最大流是多少？

下面给出相应的代码：

?
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
#include<iostream>
#include<queue>
 
using namespace std ;
 
int n , m ;
 
int map[210][210] ;
 
int path[210] ;
 
int flow[210] ;
 
 
int bfs()   {
    queue<int> q ;
    memset(path,-1,sizeof(path)) ;
    path[1] = 0 ;
    flow[1] = (1<<30) ;
    q.push(1) ;
    while(!q.empty())   {
        int t = q.front() ;
        q.pop() ;
        if(t == m) break ;
        for(int i = 2 ; i <= m ; i++)
            if(path[i] == -1 && map[t][i])  {      // 该路径没有被访问过
                flow[i]=flow[t]<map[t][i]?flow[t]:map[t][i];   // 该路径最小流量
                q.push(i) ;
                path[i] = t ;   // 存储路径
            }
    }
    if(path[m] == -1)
        return -1 ;
    return flow[m] ;
}
 
 
void Edmonds_Karp() {
    int max_flow = 0 , floww ;
     while((floww=bfs())!=-1)   {
        max_flow += floww ;
        int s , t ;
        t = m ;
        while(t != 1 )  {
            s = path[t] ;
            map[s][t] -= floww ;
            map[t][s] += floww ;
            t = s ;
        }
    }
    cout << max_flow << endl ;
}
 
 
 
int main()  {
    while(cin >> n >> m)    {
        memset(map,0,sizeof(map)) ;
        while(n--) {
            int u , v , cost ;
            cin >> u >> v >> cost ;
            map[u][v] += cost ;
        }
        Edmonds_Karp() ;
    }
    return 0 ;
}

　　


联系
我们