网络流的最大流入门（从普通算法到dinic优化）

时间：2022-05-13 19:31:12

网络流(network-flows)是一种类比水流的解决问题方法，与线性规划密切相关。网络流的理论和应用在不断发展。而我们今天要讲的就是网络流里的一种常见问题——最大流问题。
最大流问题(maximum flow problem)，一种组合最优化问题，就是要讨论如何充分利用装置的能力，使得运输的流量最大，以取得最好的效果。求最大流的标号算法最早由福特和福克逊与与1956年提出，20世纪50年代福特(Ford)、(Fulkerson)建立的“网络流理论”，是网络应用的重要组成成分。

再解决这个问题前，我们要先弄懂一些定义：

网络流的最大流入门（从普通算法到dinic优化）

网络流图是一张只有一个源点和汇点的有向图，而最大流就是求源点到汇点间的最大水流量，下图的问题就是一个最基本，经典的最大流问题

网络流的最大流入门（从普通算法到dinic优化）

二.流量，容量和可行流

对于弧(u,v)来说，流量就是其上流过的水量(我们通常用f(u,v)表示)，而容量就是其上可流过的最大水量(我们通常用c(u,v)表示)，只要满足f(u,v)<=c(u,v)，我们就称流量f(u,v)是可行流(对于最大流问题而言，所有管道上的流量必须都是可行流)。

三.增广路

网络流的最大流入门（从普通算法到dinic优化）

如果一条路上的所有边均满足:

正向边: f(u,v)< c(u,v) ——– 反向边：f(u,v)> 0

则我们称这条路径为一条增广路径，简称增广路。

好了，弄懂了一些定义，接下来就可以介绍著名的Ford-Fulkerson算法了。

网络流的最大流入门（从普通算法到dinic优化）

如图所示，如果我们每次都找出一条增广路，只要这条增广路经过汇点，那说明此时水流还可以增加，增加的量为d(d=min(d,c(u,v)-f(u,v))或d=min(d,f(u,v)))。

我们可以这样理解：对于每一条正向边，他能添加的最大水流为c(u,v)-f(u,v)。而对于反向边来说，当正向边上的水流增多时，反向边自身的反向水流会减少，而其能减少的最多水量为f(u,v)。由于要保证添加水流之后，所有的f(u,v)都是可行流，所以我们取最小值。

增加之后，我们要更新流量，每条正向边+d,每条反向边-d即可。

既然这样，我们的思路就是：

1.找出一条增广路径 ——2.修改其上点的值——3.继续重复1，直至找不出增广路。则此时源点的汇出量即为所求的最大流。

网络流的最大流入门（从普通算法到dinic优化）
网络流的最大流入门（从普通算法到dinic优化）
网络流的最大流入门（从普通算法到dinic优化）
网络流的最大流入门（从普通算法到dinic优化）
网络流的最大流入门（从普通算法到dinic优化）

那么上代码：

#include<bits/stdc++.h>
#include<vector>
#define maxn 1200
#define INF 2e9
using namespace std;
int i,j,k,n,m,h,t,tot,ans,st,en;
struct node{
    int c,f;
}edge[maxn][maxn];
int flag[maxn],pre[maxn],alpha[maxn],q[maxn],v;
int read(){
    char c;int x;while(c=getchar(),c<'0'||c>'9');x=c-'0';
    while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x;
}

void bfs(){
    memset(flag,0xff,sizeof(flag));memset(pre,0xff,sizeof(pre));memset(alpha,0xff,sizeof(alpha));
    flag[st]=0;pre[st]=0;alpha[st]=INF;h=0,t=1;q[t]=st;
    while(h<t){
        h++;v=q[h];
        for(int i=1;i<=n;i++){
            if(flag[i]==-1){
                if(edge[v][i].c<INF&&edge[v][i].f<edge[v][i].c){
                    flag[i]=0;pre[i]=v;alpha[i]=min(alpha[v],edge[v][i].c-edge[v][i].f);q[++t]=i;
                }
                else if(edge[i][v].c<INF&&edge[i][v].f>0){
                    flag[i]=0;pre[i]=-v;alpha[i]=min(alpha[v],edge[i][v].f);q[++t]=i;
                }
            }
        }
        flag[v]=1;
    }
}

void Ford_Fulkerson(){
    while(1){
        bfs();
        if(alpha[en]==0||flag[en]==-1){
            break;
        }
        int k1=en,k2=abs(pre[k1]);int a=alpha[en];
        while(1){
            if(edge[k2][k1].c<INF) edge[k2][k1].f+=a;
            else if(edge[k1][k2].c<INF) edge[k1][k2].f-=a;
            if(k2==st) break;
            k1=k2;k2=abs(pre[k1]);
        }
        alpha[en]=0;
    }
}

void flow(){
    int maxflow=0;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++){
        if(i==st&&edge[i][j].f<INF) maxflow+=edge[i][j].f;
      }
    printf("%d",maxflow);
}

int main(){
    int u,v,c,f;
    n=read();m=read();st=read();en=read();
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++) edge[i][j].c=INF,edge[i][j].f=0;
    for(int i=1;i<=m;i++){
        u=read();v=read();c=read();
        edge[u][v].c=c;
    }
    Ford_Fulkerson();
    flow();
    return 0;
}

DINIC算法

Dinic算法是网络流最大流的优化算法之一，每一步对原图进行分层，然后用DFS求增广路。时间复杂度是O(n^2*m)，Dinic算法最多被分为n个阶段，每个阶段包括建层次网络和寻找增广路两部分。

Dinic算法的思想是分阶段地在层次网络中增广。它与最短增广路算法不同之处是：最短增广路每个阶段执行完一次BFS增广后，要重新启动BFS从源点st开始寻找另一条增广路;而在Dinic算法中，只需一次BFS过程就可以实现多次增广。

简单来说，分为下面几步：

　　1.在剩余网络中查找是否存在从S到T的路径，同时建分层图。
　　　　分层图的层数其实就是S到i这个点需要几步。
　　2.沿着分层图多路增广。
　　　　增广时一定要满足dis[j]=dis[i]+1。
　　3.直到没有S到T的路径是结束算法。

链表版
#include<bits/stdc++.h>
using namespace std;

int read(){
    char c;int x;while(c=getchar(),c<'0'||c>'9');x=c-'0';
    while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x;
}

const int MAXN=10005,MAXM=100005;

int n,m,st,en,x,y,c,H,T,ans,use,cnt=0;
int nxt[MAXM*2],head[MAXN],dis[MAXN],q[MAXM*6];
struct node{
    int to,val;
}L[MAXM*2];

void add(int x,int y,int c){
    L[cnt]=(node){y,c};
    nxt[cnt]=head[x];
    head[x]=cnt;
    cnt++;
    L[cnt]=(node){x,0};
    nxt[cnt]=head[y];
    head[y]=cnt;
    cnt++;
}

int BFS(){
    H=0;T=1;q[T]=st;
    memset(dis,0,sizeof(dis));dis[st]=1;
    while(H<T){
        int front=q[++H];use=head[front];
        while(use!=-1){
            if(!dis[L[use].to]&&L[use].val){
                dis[L[use].to]=dis[front]+1;
                q[++T]=L[use].to;
            }
            use=nxt[use];
        }
    }
    return dis[en];
}

int dinic(int now,int x){
    if(now==en) return x;
    use=head[now];
    while(use!=-1){
        int rec=use;
        if(dis[L[use].to]==dis[now]+1&&L[use].val){
            int fd=dinic(L[use].to,min(x,L[use].val));
            use=rec;
            if(fd){
                L[use].val-=fd;
                L[use^1].val+=fd;
                return fd;
            }
        }
        use=nxt[rec];
    }
    return 0;
}

int main()
{
    memset(head,-1,sizeof(head));
    n=read();m=read();st=read();en=read();
    for(int i=1;i<=m;i++){
        x=read();y=read();c=read();
        add(x,y,c);
    }
    while(BFS()){
        ans+=dinic(st,2e9);
    } 
    printf("%d",ans);
    return 0;
}
vector版
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

int read(){
    char c;int x;while(c=getchar(),c<'0'||c>'9');x=c-'0';
    while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x;
}

const int MAXN=10005,MAXM=100005;

int N,M,S,T,x,y,c,ans;
int W[MAXM*2],To[MAXM*2],cnt;
int l[MAXM*5],h,t,dist[MAXN];
vector <int> a[MAXN];

bool BFS()
{
    h=t=0;
    l[++t]=S;
    memset(dist,0,sizeof(dist));dist[S]=1;
        while(h<t){
            int front=l[++h];
                for(int i=0;i<a[front].size();i++){
                    int to=a[front][i];
                    if(!dist[To[to]] && W[to]){
                        dist[To[to]]=dist[front]+1;
                        l[++t]=To[to];
                    }
                }
        }
    return dist[T];
}

int find(int now,int x)
{
    if(now==T) return x;
        for(int i=0;i<a[now].size();i++){
            int to=a[now][i];
            if(dist[To[to]]==dist[now]+1 && W[to]){
                int fd=find(To[to],min(x,W[to]));
                if(fd){
                    W[to]-=fd;
                    W[to^1]+=fd;
                    return fd;
                }
            }
        }
    return 0;
}

int main()
{
    N=read(),M=read(),S=read(),T=read();
        for(int i=1;i<=M;i++){
             x=read(),y=read(),c=read();
             W[cnt]=c,To[cnt]=y;a[x].push_back(cnt);cnt++;
             W[cnt]=0,To[cnt]=x;a[y].push_back(cnt);cnt++;
        }
        while(BFS()){
            ans+=find(S,2e9);
        }
    printf("%d",ans);
    return 0;
}
标签：

相关文章