最大流 | CS

最大流

 2019-01-14 /  Luo Jinrong

预备知识

网络：一个有向带权图，包含一个源点和一个汇点，没有反平行边（如果$v_1$和$v_2$之间有边，那么要么是$(v_1,v_2)$，要么是$(v_2,v_1)$，两个不会同时存在）。
网络流：网络流即网络上的流，是定义在网络边集$E$上的一个非负函数$flow={flow(u,v)}$，$flow(u,v)$是边上的流量。
网络最大流：在满足下面两个前提情况下，在流网络中找到一个净输出最大的网络流。

两个前提

（1）容量约束

对于所有节点u和v，满足实际流量不大于最大可容纳流量，即：$0\leq flow(u,v)\leq cap(u,v)$。

（2）流量守恒

除了源点s和汇点t外，任意节点u都满足流入量等于流出量，即：$\sum_{(x,u)\in E}flow(x,u)=\sum_{(u,y)\in E}flow(u,y)$。

对于源点s，净输出值=流出量之和-流入量之和
对于汇点t，净输入值=流入量之和-流出量之和
净输出值=净输入值

Ford-Fulkerson算法（增广路算法）

基本概念

初始网络$G$:一般体现输入的网络。
实流网络$G’$：体现当前实际流量的网络。
残余网络$G^$：$G^$和$G$的节点集相同，而网络$G$中对应$G^*$中的一条边或两条边。在残余网络中，与网络边对应的同向边是可增量（即还可以增加多少流量），反向边是实际流量。
可增广路：残余网络$G^*$中一条从源点s到汇点t的简单路径。
可增广量：可增广路上每条边的可增量的最小值。
求最大流：先在残余网络中找可增广路，然后在实流网络中增流，再在残余网络中减流。持续上述过程直至找不到可增广路。这时的实流网络就是最大流网络。

增流

沿可增广路找最小值作为可增广量d。在实流网络中沿着可增广路增流：可增广路上同向边增加流量d，反向边减少流量d。
在残余网络中沿着可增广路减流：可增广路上的同向边减少流量d，反向边增加流量d。

增广路算法

增广路定理：设flow是网络G的一个可行流，如果不存在从源点s到汇点t关于flow的可增广路p，则flow是G的一个增广路。

增广路算法其实不是一种算法，而是一种方法，因为Ford-Fulkerson并没有说明如何找可增广路，而找增广路的算法不同，算法的时间复杂度相差很大。

最短增广路算法

如何找到一条可增广路？可以设置最大容量优先，也可以是最短路径（广度优先）优先。Edmonds-Karp算法就是以广度优先的增广路算法，又称为最短增广路算法（Shortest Augument Path,SAP）。

步骤如下：

采用队列$q$来存放已访问未检查的节点。布尔数组$vis[]$标识节点是否被访问过，$pre[]$数组记录可增广路上节点的前驱，$pre[v]=u$表示可增广路上$v$节点的前驱是$u$，最大流值$maxflow=0$。

初始化可行流$flow$为零流，即实流网络中全是零流边，残余网络中全是最大容量边（可增量）。初始化$vis[]$数组为$false$，$pre[]$数组为-1。
令$vis[s]=true$，$s$加入队列$q$。
如果队列不为空，继续下一步，否则算法结束，找不到可增广路。当前的实流网络就是最大流网络，返回最大流值$maxflow$。
队头元素$new$出队，在残余网络中检查$new$的所有邻接节点$i$。如果未被访问，则访问之，令$vis[i]=true$,$pre[i]=new$；如果$i=t$，说明已到达汇点，找到一条可增广路，转向第五步；否则节点$i$加入队列$q$，转向第三步。
从汇点开始，通过前驱数组$pre[]$，逆向找可增广路上每条边值的最小值，即可增量$d$。
在实流网络中增流，在残余网络中减流，$Maxflow+=d$，转向第二步。

模板

//program 7-2
#include<iostream>
#include<queue>
#include<iomanip>
#include<cstring>
using namespace std;

const int maxn = 100; //最大顶点数
const int INF = (1<<30)-1;
int g[maxn][maxn]; //残余网络（初始时各边为容量）
int f[maxn][maxn]; //实流网络（初始时各边为0流）
int pre[maxn]; //前驱数组
bool vis[maxn];//访问数组
int n,m; //顶点个数n和边的数量m

bool bfs(int s,int t)
{
    memset(pre,-1,sizeof(pre));
    memset(vis,false,sizeof(vis));
    queue<int>q;
    vis[s]=true;
    q.push(s);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=1;i<=n; i++)//寻找可增广路
        {
            if(!vis[i]&&g[now][i]>0)//未被访问且有边相连
            {
                vis[i] = true;
                pre[i] = now;
                if(i==t)  return true;//找到一条可增广路
                q.push(i);
            }
        }
    }
    return false;//找不到可增广路
}

int EK(int s, int t)
{
    int v,w,d,maxflow;
    maxflow = 0;
    while(bfs(s,t))//可以增广
    {
        v=t;
        d=INF;
        while(v!=s)//找可增量d
        {
            w=pre[v];//w记录v的前驱
            if(d>g[w][v])
                d=g[w][v];
            v=w;
        }
        maxflow+=d;
        v=t;
        while(v!=s)//沿可增广路增流
        {
            w=pre[v];
            g[w][v]-=d;  //残余网络中正向边减流
            g[v][w]+=d;  //残余网络中反向边增流
            if(f[v][w]>0) //实流网络中如果是反向边,则减流,否则正向边增流
                f[v][w]-=d;
            else
                f[w][v]+=d;
            v=w;
         }
    }
    return maxflow;
}
void print()//输出实流网络
{
    cout<<endl;
    cout<<"----------实流网络如下：----------"<<endl;
    cout<<"  ";
    for(int i=1;i<=n;i++)
       cout<<setw(7)<<"v"<<i;
    cout<<endl;
    for(int i=1;i<=n;i++)
    {
        cout<<"v"<<i;
        for(int j=1;j<=n;j++)
           cout<<setw(7)<<f[i][j]<<" ";
        cout<<endl;
    }
}
int main()
{
    int u,v,w;
    memset(g,0,sizeof(g));//残余网络初始化为0
    memset(f,0,sizeof(f));//实流网络初始化为0
    cout<<"请输入结点个数n和边数m:"<<endl;
    cin>>n>>m;
    cout<<"请输入两个结点u,v及边(u--v)的容量w:"<<endl;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        g[u][v]+=w;
    }
    cout<<"网络的最大流值:"<<EK(1,n)<<endl;
    print();//输出实流网络
    return 0;
}

重贴标签算法（Improved Shortest Augument Path，ISAP）

步骤

确定合适的数据结构，采用邻接表存储网络。
对网络节点贴标签，即标高操作。
如果源点的高度$\ge$节点数，则转向第六步；否则从源点开始，沿着高度h(u)=h(v)+1且有可行邻接边(cap>flow)的方向前进，如果到达汇点，则转向第四步；如果无法行进，则转向第五步。
增流操作：沿着找到的增广路同向边增流，反向边减流。注意：在原网络上操作。
重贴标签：如果拥有当前节点高度的节点只有一个，则转向第六步；令当前节点的高度=所有邻接点高度的最小值+1；如果没有可行邻接边，则令当前节点的高度=节点数；退回一步；转向第三部。
算法结束，已找到最大流。

模板

//program 7-2-1 ISAP算法优化
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int inf = 0x3fffffff;
const int N=100;
const int M=10000;
int top;
int h[N], pre[N], g[N];

struct Vertex
{
   int first;
}V[N];
struct Edge
{
   int v, next;
   int cap, flow;
}E[M];
void init()
{
    memset(V, -1, sizeof(V));
    top = 0;
}
void add_edge(int u, int v, int c)
{
    E[top].v = v;
    E[top].cap = c;
    E[top].flow = 0;
    E[top].next = V[u].first;
    V[u].first = top++;
}
void add(int u,int v, int c)
{
    add_edge(u,v,c);
    add_edge(v,u,0);
}
void set_h(int t,int n)
{
    queue<int> Q;
    memset(h, -1, sizeof(h));
    memset(g, 0, sizeof(g));
    h[t] = 0;
    Q.push(t);
    while(!Q.empty())
    {
       int v = Q.front(); Q.pop();
       ++g[h[v]];
       for(int i = V[v].first; ~i; i = E[i].next)
       {
          int u = E[i].v;
          if(h[u] == -1)
          {
             h[u] = h[v] + 1;
             Q.push(u);
           }
        }
    }
    cout<<"初始化高度"<<endl;
    cout<<"h[ ]=";
    for(int i=1;i<=n;i++)
       cout<<"  "<<h[i];
    cout<<endl;
}
int Isap(int s, int t,int n)
{
    set_h(t,n);
    int ans=0, u=s;
    int d;
    while(h[s]<n)
    {
        int i=V[u].first;
        if(u==s)
           d=inf;
        for(; ~i; i=E[i].next)
        {
           int v=E[i].v;
           if(E[i].cap>E[i].flow && h[u]==h[v]+1)
           {
                u=v;
                pre[v]=i;
                d=min(d, E[i].cap-E[i].flow);
                if(u==t)
                {
                   cout<<endl;
                   cout<<"增广路径："<<t;
                   while(u!=s)
                   {
                       int j=pre[u];
                       E[j].flow+=d;
                       E[j^1].flow-=d;
                       u=E[j^1].v;
                       cout<<"--"<<u;
                   }
                   cout<<"增流："<<d<<endl;
                   ans+=d;
                   d=inf;
                }
                break;
            }
        }
        if(i==-1)
        {
           if(--g[h[u]]==0)
              break;
           int hmin=n-1;
           //cur[u]=V[u].first;
           for(int j=V[u].first; ~j; j=E[j].next)
              if(E[j].cap>E[j].flow)
                 hmin=min(hmin, h[E[j].v]);
           h[u]=hmin+1;
           cout<<"重贴标签后高度"<<endl;
           cout<<"h[ ]=";
           for(int i=1;i<=n;i++)
              cout<<"  "<<h[i];
           cout<<endl;
           ++g[h[u]];
           if(u!=s)
              u=E[pre[u]^1].v;
        }
    }
    return ans;
}
void printg(int n)//输出网络邻接表
{
   cout<<"----------网络邻接表如下：----------"<<endl;
   for(int i=1;i<=n;i++)
   {
       cout<<"v"<<i<<"  ["<<V[i].first;
       for(int j=V[i].first;~j;j=E[j].next)
           cout<<"]--["<<E[j].v<<"   "<<E[j].cap<<"   "<<E[j].flow<<"   "<<E[j].next;
       cout<<"]"<<endl;

   }

}
void printflow(int n)//输出实流边
{
   cout<<"----------实流边如下：----------"<<endl;
   for(int i=1;i<=n;i++)
     for(int j=V[i].first;~j;j=E[j].next)
        if(E[j].flow>0)
        {
           cout<<"v"<<i<<"--"<<"v"<<E[j].v<<"   "<<E[j].flow;
           cout<<endl;
        }
}

int main()
{
    int n, m;
    int u, v, w;
    cout<<"请输入结点个数n和边数m:"<<endl;
    cin>>n>>m;
    init();
    cout<<"请输入两个结点u,v及边(u--v)的容量w:"<<endl;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        add(u, v, w);
    }
    cout<<endl;
    printg(n);//输出初始网络邻接表
    cout<<"网络的最大流值:"<<Isap(1,n,n)<<endl;
    cout<<endl;
    printg(n);//输出最终网络
    printflow(n);//输出实流边
    return 0;
}

本文链接：
https://luojinrong.github.io/2019/01/14/最大流/