网络流入门

2017-08-04 本文已影响0人 Gitfan

源点：有n个点，有m条有向边，有一个点很特殊，只出不进，叫做源点。
汇点：另一个点也很特殊，只进不出，叫做汇点。
容量和流量：每条有向边上有两个量，容量和流量，从i到j的容量通常用c[i,j]表示,流量则通常是f[i,j].

通常可以把这些边想象成道路，流量就是这条道路的车流量，容量就是道路可承受的最大的车流量。很显然的，流量<=容量。而对于每个不是源点和汇点的点来说，可以类比的想象成没有存储功能的货物的中转站，所有“进入”他们的流量和等于所有从他本身“
出去”的流量。

最大流：把源点比作工厂的话，问题就是求从工厂最大可以发出多少货物，是不至于超过道路的容量限制，也就是，最大流。

网络流基础篇——Edmond-Karp算法

求解思路：
首先，假如所有边上的流量都没有超过容量(不大于容量)，那么就把这一组流量，或者说，这个流，称为一个可行流。
一个最简单的例子就是，零流，即所有的流量都是0的流。

(1).我们就从这个零流开始考虑，假如有这么一条路，这条路从源点开始一直一段一段的连到了
汇点，并且，这条路上的每一段都满足流量<容量，注意，是严格的<,而不是<=。
(2).那么，我们一定能找到这条路上的每一段的(容量-流量)的值当中的最小值delta。我们把这条路上每一段的流量都加上这个delta，一定可以保证这个流依然是可行流，这是显然的。
(3).这样我们就得到了一个更大的流，他的流量是之前的流量+delta，而这条路就叫做增广路。我们不断地从起点开始寻找增广路，每次都对其进行增广，直到源点和汇点不连通，也就是找不到增广路为止。
(4).当找不到增广路的时候，当前的流量就是最大流，这个结论非常重要。

补充：

(1).寻找增广路的时候我们可以简单的从源点开始做BFS，并不断修改这条路上的delta 量，直到找到源点或者找不到增广路。
(2).在程序实现的时候，我们通常只是用一个c 数组来记录容量，而不记录流量，当流量+delta 的时候，我们可以通过容量-delta 来实现，以方便程序的实现。

相关问题：

为什么要增加反向边？
在做增广路时可能会阻塞后面的增广路，
或者说，做增广路本来是有个顺序才能找完最大流的。

但我们是任意找的，为了修正，就每次将流量加在了反向弧上，让后面的流能够进行自我调整。

举例：
比如说下面这个网络流模型

2017-08-16 11-37-02.png

我们第一次找到了1-2-3-4这条增广路，这条路上的delta值显然是1。
于是我们修改后得到了下面这个流。（图中的数字是容量）

2017-08-16 11-38-05.png

这时候(1,2)和(3,4)边上的流量都等于容量了，我们再也找不到其他的增广路了，当前的流量是1。

但是，

这个答案明显不是最大流，因为我们可以同时走1-2-4和1-3-4，这样可以得到流量为2的流。

那么我们刚刚的算法问题在哪里呢？

问题就在于我们没有给程序一个“后悔”的机会，应该有一个不走(2-3-4)而改走(2-4)的机制。

那么如何解决这个问题呢？

我们利用一个叫做反向边的概念来解决这个问题。即每条边(i,j)都有一条反向边(j,i)，反向边也同样有它的容量。
我们直接来看它是如何解决的：
在第一次找到增广路之后，在把路上每一段的容量减少delta的同时，也把每一段上的反方向的容量增加delta。

c[x,y]-=delta;

c[y,x]+=delta;

我们来看刚才的例子，在找到1-2-3-4这条增广路之后，把容量修改成如下：

2017.jpg

这时再找增广路的时候，就会找到1-3-2-4这条可增广量，即delta值为1的可增广路。将这条路增广之后，得到了最大流2。

2017.jpg

那么，这么做为什么会是对的呢？

事实上，当我们第二次的增广路走3-2这条反向边的时候，就相当于把2-3这条正向边已经是用了的流量给“退”了回去，不走2-3这条路，而改走从2点出发的其他的路也就是2-4。

如果这里没有2-4怎么办？

这时假如没有2-4这条路的话，最终这条增广路也不会存在，因为他根本不能走到汇点
同时本来在3-4上的流量由1-3-4这条路来“接管”。而最终2-3这条路正向流量1，反向流量1，等于没有流。

A - Drainage Ditches
一道网络流裸题

Edmonds_Karp 算法邻接矩阵

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=205;
const int INF=0x3f3f3f3f;
int graph[MAXN][MAXN];
int pre[MAXN];
int vis[MAXN];
int n,m;
int BFS(int st,int ed)
{
    memset(vis,0,sizeof(vis));
    queue<int> que;
    que.push(st);
    vis[st]=1;
    int curr,flow=INF;
    pre[st]=pre[ed]=-1;
    while(!que.empty())
    {
        curr=que.front();
        que.pop();
        if(curr==ed) break;
        for(int nxt=1;nxt<=n;nxt++)
        {
            if(vis[nxt]==0&&graph[curr][nxt]!=0)
            {
                vis[nxt]=1;
                if(flow>graph[curr][nxt]) flow=graph[curr][nxt];
                pre[nxt]=curr;
                que.push(nxt);
            }
        }
    }
    if(pre[ed]==-1) return 0;
    return flow;
}
int Edmonds_Karp(int st,int ed)
{
    int stream;
    int sum=0;
    while((stream=BFS(st,ed))!=0)
    {
        int u=ed;
        while(pre[u]!=-1)
        {
            graph[pre[u]][u]-=stream;
            graph[u][pre[u]]+=stream;
            u=pre[u];
        }
        sum+=stream;
    }
    return sum;
}
int main()
{
    int a,b,flow;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(graph,0,sizeof(graph));
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&flow);
            graph[a][b]+=flow;
            //注意,这里的a,b节点都是独一无二的节点(包含分裂的节点)
            //比如原来有x个节点,通过分裂这x个节点构图,那么n=2*x,即有2*x个不同的节点
        }
        printf("%d\n",Edmonds_Karp(1,n));
    }
}

Edmonds_Karp算法前向星

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=1010;
const int MAXE=5010;
const int INF=0x3f3f3f3f;
int head[MAXN],cnt;
struct Node
{
    int to,next,val;
    Node(){}
    Node(int to,int next,int val):to(to),next(next),val(val){}
};
Node edge[MAXE];
void addEdge(int u,int v,int val)
{
    edge[cnt]=Node(v,head[u],val);
    head[u]=cnt++;
    edge[cnt]=Node(u,head[v],0);
    head[v]=cnt++;
}
int vis[MAXN],pre[MAXN];
int BFS(int st,int ed)
{
    memset(vis,0,sizeof(vis));
    vis[st]=1;
    queue<int> que;
    que.push(st);
    int u,v,flow=INF;
    pre[st]=pre[ed]=-1;
    while(!que.empty())
    {
        u=que.front();
        que.pop();
        if(u==ed) break;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].to;
            if(vis[v]==0&&edge[i].val>0)
            {
                vis[v]=1;
                flow=min(flow,edge[i].val);
                pre[v]=i;//注意寻路方式
                que.push(v);
            }
        }
    }
    if(pre[ed]==-1) return 0;
    return flow;
}
int Edmonds_Karp(int st,int ed)
{
    int stream,flow=0;
    while((stream=BFS(st,ed))!=0)
    {   //pre通过节点存边的坐标,通过边的反向边的to获取上一个节点
        for(int i=pre[ed];i!=-1;i=pre[edge[i^1].to])
        {
            edge[i].val-=stream;
            edge[i^1].val+=stream;
        }
        flow+=stream;
    }
    return flow;
}
int main()
{
    int a,b,n,m,flow;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(head,-1,sizeof(head));
        cnt=0;
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&flow);
            addEdge(a,b,flow);
        }
        printf("%d\n",Edmonds_Karp(1,n));
    }
    return 0;
}

Edmonds_Karp算法很难用邻接表描述,因为通过BFS得出一个pre数组,但是pre数组给出的某个顶点u和它的前一个顶点v,理论上我们要为v --> u 这条边减去相应的容量,u --> v这条边要添加相应的容量,但是我们不知道这两条边在邻接表的位置;解决办法有另开一个二维数组存储u-->v和v-->u在邻接表的位置,这样子还不如用邻接矩阵划算...
Ford_Fulkerson算法邻接矩阵

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=0x7fffffff;
const int MAXN=205;
int graph[MAXN][MAXN];
int vis[MAXN];
int n,m;
int dfs(int st,int ed,int f)
{
    vis[st]=1;
    if(st==ed) return f;
    for(int i=1;i<=n;i++)
    {
        if(graph[st][i]>0&&vis[i]==0)
        {
            int d=dfs(i,ed,min(graph[st][i],f));
            if(d>0)
            {
                graph[st][i]-=d;
                graph[i][st]+=d;
                return d;
            }
        }
    }
    return 0;
}
int Ford_Fulkerson(int st,int ed)
{
    int flow=0,curr;
    while(true)
    {
        memset(vis,0,sizeof(vis));
        curr=dfs(st,ed,INF);
        if(curr==0) return flow;
        flow+=curr;
    }
}
int main()
{
    int a,b,val;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(graph,0,sizeof(graph));
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&val);
            graph[a][b]+=val;
        }
        printf("%d\n",Ford_Fulkerson(1,n));
    }
    return 0;
}

Ford_Fulkerson算法邻接表

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<vector>
using namespace std;
const int INF=0x7fffffff;
const int MAXN=205;
struct Node
{
    int to;
    int flow;
    int rev;//反向边在数组的位置
    Node(){}
    Node(int to,int flow,int rev):to(to),flow(flow),rev(rev){}
};
vector<Node> graph[MAXN];
int vis[MAXN];
int n,m;
void addEdge(int from,int to,int val)
{
    graph[from].push_back(Node(to,val,graph[to].size()));
    graph[to].push_back(Node(from,0,graph[from].size()-1));//反向边的流量为0
}
int dfs(int st,int ed,int f)
{
    vis[st]=1;
    if(st==ed) return f;
    for(int i=0;i<graph[st].size();i++)
    {
        Node &temp=graph[st][i];//必须用引用
        if(vis[temp.to]==0&&temp.flow>0)
        {
            int d=dfs(temp.to,ed,min(f,temp.flow));
            if(d>0)
            {
                temp.flow-=d;
                graph[temp.to][temp.rev].flow+=d;
                return d;
            }
        }
    }
    return 0;
}
int Ford_Fulkerson(int st,int ed)
{
    int flow=0,curr;
    while(true)
    {
        memset(vis,0,sizeof(vis));
        curr=dfs(st,ed,INF);
        if(curr==0) return flow;
        flow+=curr;
    }
}
int main()
{
    int a,b,val;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            graph[i].clear();
        }
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&val);
            addEdge(a,b,val);
        }
        printf("%d\n",Ford_Fulkerson(1,n));
    }
    return 0;
}

Ford_Fulkerson算法前向星

#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=210;
const int INF=0x7fffffff;
struct Node
{
    int to;
    int next;
    int c;
};
Node Edge[MAXN*2];
int head[MAXN];
int vis[MAXN];
int cnt;
void addEdge(int u,int v,int val)
{
    Edge[cnt].to=v;
    Edge[cnt].c=val;
    Edge[cnt].next=head[u];
    head[u]=cnt++;
    Edge[cnt].to=u;//添加反向边,流量为0
    Edge[cnt].c=0;
    Edge[cnt].next=head[v];
    head[v]=cnt++;
}
int DFS(int st,int ed,int f)
{
    vis[st]=1;
    if(st==ed) return f;
    for(int i=head[st];i!=-1;i=Edge[i].next)
    {
        if(Edge[i].c>0&&vis[Edge[i].to]==0)
        {
            int d=DFS(Edge[i].to,ed,min(Edge[i].c,f));
            if(d>0)
            {
                Edge[i].c-=d;
                Edge[i^1].c+=d;//添边的时候反向边正好在数组的相邻位置,所以i^1是取反向边
                return d;
            }
        }
    }
    return 0;
}
int Ford_Fulkerson(int st,int ed)
{
    int flow=0,d,u;
    while(true)
    {
        memset(vis,0,sizeof(vis));
        d=DFS(st,ed,INF);
        if(d==0) break;
        flow+=d;
    }
    return flow;
}
int main()
{
    int n,m,a,b,val;
    while(scanf("%d%d",&m,&n)!=EOF)
    {

        memset(head,-1,sizeof(head));
        cnt=0;
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&val);
            addEdge(a,b,val);
        }
        printf("%d\n",Ford_Fulkerson(1,n));
    }
}

Dinic算法邻接矩阵

#include <cstdio>
#include <string.h>
#include <queue>
#include<cstring>
using namespace std;
const int INF = 0x7fffffff;
const int MAX = 205;
int c[MAX][MAX];
int step[MAX];
int n,m;
bool BFS(int st,int ed)
{
    memset(step,-1,sizeof(step));
    queue<int> que;
    step[st]=0;
    que.push(st);
    while(!que.empty())
    {
        int curr=que.front();
        que.pop();
        for(int i=1;i<=n;i++)
        {
            if(c[curr][i]>0&&(step[i]==-1))//i没访问过
            {
                step[i]=step[curr]+1;
                if(i==ed) return true;
                que.push(i);
            }
        }
    }
    return step[ed]!=-1;
}
int DFS(int st,int ed,int f)
{
    if(st==ed||f==0) return f;
    int flow=0,d;
    for(int i=1;i<=n;i++)
    {
        if((step[i]==step[st]+1)&&c[st][i]>0&&(d=DFS(i,ed,min(c[st][i],f))))
        {
                c[st][i]-=d;
                c[i][st]+=d;
                flow+=d;         //累加当前节点的某条路径的合适流量
                f-=d;            //当前节点的容量减去某条路径的合适流量
                if(f==0) break;  //如果当前节点的容量用完,说明无法再通过任何流量
        }
    }
    if(flow==0) step[st]=INF;//如果当前节点无任何流量通过,取消标记
    return flow;
}
int Dinic(int st,int ed)
{
    int flow=0;
    while(BFS(st,ed))
    {
        flow+=DFS(st,ed,INF);
    }
    return flow;
}
int main()
{
    int a,b,flow;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(c,0,sizeof(c));
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&flow);
            c[a][b]+=flow;
        }
        printf("%d\n",Dinic(1,n));
    }
    return 0;
}

Dinic算法邻接表

#include <cstdio>
#include <queue>
#include<cstring>
#include<vector>
using namespace std;
const int INF = 0x7fffffff;
const int MAX = 205;
int step[MAX];
struct Node
{
    int to;
    int flow;
    int rev;//记录反向边的index
    Node(){}
    Node(int to,int flow,int rev):to(to),flow(flow),rev(rev){}
};
vector<Node> graph[MAX];
int n,m;
void addEdge(int from,int to,int flow)
{
    graph[from].push_back(Node(to,flow,graph[to].size()));
    graph[to].push_back(Node(from,0,graph[from].size()-1));
}
bool BFS(int st,int ed)
{
    memset(step,-1,sizeof(step));
    queue<int> que;
    que.push(st);
    step[st]=0;
    while(!que.empty())
    {
        int curr=que.front();
        que.pop();
        for(int i=0;i<graph[curr].size();i++)
        {
            Node &temp=graph[curr][i];
            if(step[temp.to]==-1&&temp.flow>0)
            {
                step[temp.to]=step[curr]+1;
                if(temp.to==ed) return true;
                que.push(temp.to);
            }
        }
    }
    return step[ed]!=-1;
}
int DFS(int st,int ed,int f)
{
    if(st==ed||f==0) return f;
    int flow=0;
    for(int i=0;i<graph[st].size();i++)
    {
        Node &temp=graph[st][i];
        if(temp.flow>0&&step[temp.to]==step[st]+1)
        {
            int d=DFS(temp.to,ed,min(f,temp.flow));
            if(d>0)
            {
                temp.flow-=d;
                graph[temp.to][temp.rev].flow+=d;
                flow+=d;         //累加当前节点的某条路径的合适流量
                f-=d;            //当前节点的容量减去某条路径的合适流量
                if(f==0) break;  //如果当前节点的容量用完,说明无法再通过任何流量
            }
        }
    }
    if(flow==0) step[st]=INF;//如果当前节点无任何流量通过,取消标记
    return flow;
}
int Dinic(int st,int ed)
{
    int flow=0;
    while(BFS(st,ed))
    {
       flow+=DFS(st,ed,INF);
    }
    return flow;
}
int main()
{

    int a,b,flow;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(graph,0,sizeof(graph));
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&flow);
            addEdge(a,b,flow);
        }
        printf("%d\n",Dinic(1,n));
    }
    return 0;
}

Dinic算法前向星

#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=1010;
const int INF=0x7fffffff;
struct Node
{
    int to;
    int next;
    int c;
};
Node Edge[MAXN*2];//因为要建立反向边,所以边的数目要为两倍
int head[MAXN];
int step[MAXN];
int cnt;
void addEdge(int u,int v,int val)
{
    Edge[cnt].to=v;
    Edge[cnt].next=head[u];
    Edge[cnt].c=val;
    head[u]=cnt++;
    Edge[cnt].to=u;
    Edge[cnt].c=0;
    Edge[cnt].next=head[v];
    head[v]=cnt++;
}
bool BFS(int st,int ed)
{
    queue<int> que;
    que.push(st);
    memset(step,-1,sizeof(step));
    step[st]=0;
    int u,i;
    while(!que.empty())
    {
        u=que.front();
        que.pop();
        for(i=head[u];i!=-1;i=Edge[i].next)
        {
            if(step[Edge[i].to]==-1&&Edge[i].c>0)
            {
                step[Edge[i].to]=step[u]+1;
                que.push(Edge[i].to);
                if(Edge[i].to==ed) return true;
            }
        }
    }
    return step[ed]!=-1;
}
int DFS(int st,int ed,int flow)
{
    if(st==ed||!flow) return flow;
    int curr=0;
    for(int i=head[st];i!=-1;i=Edge[i].next)
    {
        if(step[st]+1==step[Edge[i].to]&&Edge[i].c>0)
        {
            int d=DFS(Edge[i].to,ed,min(Edge[i].c,flow));
            if(d>0)
            {
                Edge[i].c-=d;
                Edge[i^1].c+=d;//添反向边的时候是相邻的,i^1取相邻数;
                curr+=d;       //累加当前节点的某条路径的合适流量
                flow-=d;       //当前节点的容量减去某条路径的合适流量
                if(flow==0) break;//如果当前节点的容量用完,说明无法再通过任何流量
            }
        }
    }
    if(curr==0) step[st]=INF;//如果当前节点无任何流量通过,取消标记
    return curr;
}
int Dinic(int st,int ed)
{
    int flow=0;
    while(BFS(st,ed))
    {
       flow+=DFS(st,ed,INF);
    }
    return flow;
}
int main()
{
    int n,m,a,b,val;
    while(scanf("%d%d",&m,&n)!=EOF)
    {

        memset(head,-1,sizeof(head));
        cnt=0;
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&val);
            addEdge(a,b,val);
        }
        printf("%d\n",Dinic(1,n));
    }
}

网络流入门

但是，

那么我们刚刚的算法问题在哪里呢？

那么如何解决这个问题呢？

那么，这么做为什么会是对的呢？

如果这里没有2-4怎么办？

猜你喜欢

热点阅读

网络流入门

但是，

那么我们刚刚的算法问题在哪里呢？

那么如何解决这个问题呢 ？

那么，这么做为什么会是对的呢？

如果这里没有2-4怎么办？

猜你喜欢

热点阅读

那么如何解决这个问题呢？