最大流之sap算法

dopost

　　若有向图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

求最大流是多少？

下面给出相应的代码：

#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 == -1 && map[t]){      // 该路径没有被访问过
flow=flow[t]<map[t]?flow[t]:map[t];   // 该路径最小流量
q.push(i) ;
path = 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[t] -= floww ;
map[t] += 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[v] += cost ;
}
Edmonds_Karp() ;
}
return 0 ;
}