网络流求最大流_最大流问题对网络图的要求

以poj 1273 为例

第一个隆重登场的算法是 EK（Edmond—Karp）算法

感谢http://www.cnblogs.com/zsboy/archive/2013/01/27/2878810.html 的博文，里面有很详细的我要给出的第一个代码的模板和对于该算法的深刻理解

先给出模板（也是为了方便以后自己查阅）

<strong><span style = "font-size:12px;">#include <iostream>

#include <queue>
#include<string.h>
using namespace std;

#define arraysize 201
int maxData = 0x7fffffff;
int capacity[arraysize][arraysize]; //记录残留网络的容量
int flow[arraysize]; //标记从源点到当前节点实际还剩多少流量可用
int pre[arraysize]; //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中
int n, m;
queue<int> myqueue;

int BFS(int src, int des)
{
    int i, j;
    while(!myqueue.empty()) //队列清空
        myqueue.pop();
    for(i = 1; i < m + 1; ++i)
    {
        pre[i] = -1;
    }
    pre[src] = 0;
    flow[src] = maxData;
    myqueue.push(src);
    while(!myqueue.empty())
    {
        int index = myqueue.front();
        myqueue.pop();
        if(index == des) //找到了增广路径
            break;
        for(i = 1; i < m + 1; ++i)
        {
            if(i != src && capacity[index][i] > 0 && pre[i] == -1)
            {
                pre[i] = index; //记录前驱
                flow[i] = min(capacity[index][i], flow[index]); //关键：迭代的找到增量
                myqueue.push(i);
            }
        }
    }
    if(pre[des] == -1) //残留图中不再存在增广路径
        return -1;
    else
        return flow[des];
}
int maxFlow(int src, int des)
{
    int increasement = 0;
    int sumflow = 0;
    while((increasement = BFS(src, des)) != -1)
    {
        int k = des; //利用前驱寻找路径
        while(k != src)
        {
            int last = pre[k];
            capacity[last][k] -= increasement; //改变正向边的容量
            capacity[k][last] += increasement; //改变反向边的容量
            k = last;
        }
        sumflow += increasement;
    }
    return sumflow;
}
int main()
{
    int i, j;
    int start, end, ci;
    while(cin >> n >> m)
    {
        memset(capacity, 0, sizeof(capacity));
        memset(flow, 0, sizeof(flow));
        for(i = 0; i < n; ++i)
        {
            cin >> start >> end >> ci;
            if(start == end) //考虑起点终点相同的情况
                continue;
            capacity[start][end] += ci; //此处注意可能出现多条同一起点终点的情况
        }
        cout << maxFlow(1, m) << endl;
    }
    return 0;
} < / span > < / strong >

EK算法的核心
反复寻找源点s到汇点t之间的增广路径，若有，找出增广路径上每一段[容量-流量]的最小值delta，若无，则结束。
在寻找增广路径时，可以用BFS来找，并且更新残留网络的值(涉及到反向边)。
而找到delta后，则使最大流值加上delta，更新为当前的最大流值。

对于BFS找增广路：

1.         flow[1]=INF，pre[1]=0;

        源点1进队列，开始找增广路，capacity[1][2]=40>0，则flow[2]=min(flow[1],40)=40;

        capacity[1][4]=20>0,则flow[4]=min(flow[1],20)=20;

        capacity[2][3]=30>0,则flow[3]=min(folw[2]=40，30)=30；

        capacity[2][4]=30,但是pre[4]=1(已经在capacity[1][4]这遍历过4号点了)

        capacity[3][4]…..

        当index=4（汇点），结束增广路的寻找

        传递回increasement（该路径的流），利用前驱pre寻找路径

路径也自然变成了这样：

2.flow[1]=INF，pre[1]=0;

 源点1进队列，开始找增广路，capacity[1][2]=40>0，则flow[2]=min(flow[1],40)=40;

        capacity[1][4]=0!>0,跳过

        capacity[2][3]=30>0,则flow[3]=min(folw[2]=40，30)=30；

        capacity[2][4]=30,pre[4]=2，则flow[2][4]=min(flow[2]=40,20)=20;

        capacity[3][4]…..

        当index=4（汇点），结束增广路的寻找

        传递回increasement（该路径的流），利用前驱pre寻找路径

 图也被改成

接下来同理

这就是最终完成的图，最终sumflow=20+20+10=50（这个就是最大流的值）

第二个隆重登场的算法，Ford-Fulkerson算法，简单易懂，老少皆宜

基于邻接矩阵的一个模板

<strong><span style="font-size:12px;">#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int map[300][300];
int used[300];
int n,m;
const int INF = 1000000000;
int dfs(int s,int t,int f)
{
    if(s == t) return f;
    for(int i = 1 ; i <= n ; i ++) {
        if(map[s][i] > 0 && !used[i]) {
            used[i] = true;
            int d = dfs(i,t,min(f,map[s][i]));
            if(d > 0) {
                map[s][i] -= d;
                map[i][s] += d;
                return d;
            }
        }
    }
    return 0;
}
int maxflow(int s,int t)
{
    int flow = 0;
    while(true) {
        memset(used,0,sizeof(used));
        int f = dfs(s,t,INF);//不断找从s到t的增广路
        if(f == 0) return flow;//找不到了就回去
        flow += f;//找到一个流量f的路
    }
}
int main()
{
    while(scanf("%d%d",&m,&n) != EOF) {
        memset(map,0,sizeof(map));
        for(int i = 0 ; i < m ; i ++) {
            int from,to,cap;
            scanf("%d%d%d",&from,&to,&cap);
            map[from][to] += cap;
        }
        cout << maxflow(1,n) << endl;
    }
    return 0;</span>
}</strong>

基于邻接表的模版:

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;

const int maxn = 400;
const int inf = 0x3f3f3f3f;
struct node{
    int v,cap;
    node(int v,int cap):v(v),cap(cap){}
};
vector<node> edges;
vector<int> G[maxn];
int vis[maxn];
int n,m;

int dfs(int s,int t,int flow){
    if(s == t) return flow;
    vis[s] = 1;
    for(int i = 0;i < G[s].size();i ++){
        node &e = edges[G[s][i]];
        if(e.cap > 0 && !vis[e.v]){
            int d = dfs(e.v,t,min(flow,e.cap));
            if(d > 0){
                edges[G[s][i]].cap -= d;
                edges[G[s][i]^1].cap += d;
                return d;
            }
        }
    }
    return 0;
}

void add(int u,int v,int cap){
    edges.push_back(node(v,cap));
    edges.push_back(node(u,0));
    int s = edges.size();
    G[u].push_back(s - 2);        //一对边，相邻着放, 这样  ^1 就可以得到其反向边
    G[v].push_back(s - 1);
}

int maxflow(int s,int t){
    int sum = 0;
    while(1){
        memset(vis,0,sizeof(vis));
        int addflow = dfs(s,t,inf);
        if(addflow == 0) break;
        sum += addflow;
    }
    return sum;
}

int main()
{
    while(~scanf("%d%d",&n,&m)){
        for(int i = 0;i < maxn;i ++) G[i].clear();
        edges.clear();
        int s,e,c;
        for(int i = 0;i < n;i ++){
            scanf("%d%d%d",&s,&e,&c);
            if(s == e) continue;
            add(s,e,c);
        }
        printf("%d\n",maxflow(1,m));
    }
    return 0;
}

第三种方法：Dinic算法，可以看作是两种方法的结合体，它进行了一定的优化，对于某些横边多的图，运行速度方面得到了大幅提升

Dinic算法的基本思路:

       根据残量网络计算层次图。

       在层次图中使用DFS进行增广直到不存在增广路

       重复以上步骤直到无法增广 

• 层次图:分层图,以[从原点到某点的最短距离]分层的图,距离相等的为一层,(比如上图的分层为{1},{2,4},{3})

       观察前面的dfs算法，对于层次相同的边，会经过多次重复运算，很浪费时间，那么，可以考虑先对原图分好层产生新的层次图，即保存了每个点的层次，注意，很多人会把这里的边的最大容量跟以前算最短路时的那个权值混淆，其实这里每个点之间的距离都可以看作单位距离，然后对新图进行dfs，这时的dfs就非常有层次感，有筛选感了，同层次的点不可能在同一跳路径中，直接排除。那么运行速度就会快很多了。

<span style="font-size:12px;"><strong>#include <cstdio>
#include <string.h>
#include <queue>
using namespace std;
int const inf = 0x3f3f3f3f;
int const MAX = 205;
int n, m;
int c[MAX][MAX], dep[MAX];//dep[MAX]代表当前层数
 
int bfs(int s, int t)//重新建图，按层次建图
{
    queue<int> q;
    while(!q.empty())
        q.pop();
    memset(dep, -1, sizeof(dep));
    dep[s] = 0;
    q.push(s);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int v = 1; v <= m; v++){
            if(c[u][v] > 0 && dep[v] == -1){//如果可以到达且还没有访问，可以到达的条件是剩余容量大于0，没有访问的条件是当前层数还未知
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    }
    return dep[t] != -1;
}
 
int dfs(int u, int mi, int t)//查找路径上的最小流量
{
    if(u == t)
        return mi;
    int tmp;
    for(int v = 1; v <= m; v++){
        if(c[u][v] > 0 && dep[v] == dep[u] + 1  && (tmp = dfs(v, min(mi, c[u][v]), t))){
            c[u][v] -= tmp;
            c[v][u] += tmp;
            return tmp;
        }
    }
    return 0;
}
 
int dinic()
{
    int ans = 0, tmp;
    while(bfs(1, m)){
        while(1){
            tmp = dfs(1, inf, m);
            if(tmp == 0)
                break;
            ans += tmp;
        }
    }
    return ans;
}
 
int main()
{
    while(~scanf("%d %d", &n, &m)){
        memset(c, 0, sizeof(c));
        int u, v, w;
        while(n--){
            scanf("%d %d %d", &u, &v, &w);
            c[u][v] += w;
        }
        printf("%d\n", dinic());
    }
    return 0;
}</strong></span>

转载自:网络流最大流入门3种算法

今天的文章网络流求最大流_最大流问题对网络图的要求分享到此就结束了，感谢您的阅读。