算法笔记之线性规划网络流问题（3）

优化扩展——重贴标签算法ISAP

首先对所有的结点标记到汇点的最短距离，称之为高度。标高从汇点开始，用BFS方式，汇点的邻接点高度为1，继续访问的结点高度是2，一直到源点结束。

贴好标签之后，就可以从源点开始，沿着高度h(u)=h(v)+1且具有可行邻接边（cap>flow)的方向前进。我们找到了1-2-4-6。

我们再次从源点开始搜索，沿着高度h(u)=h(v)+1且具有可行邻接边（cap>flow)的方向前进，h(1)=3,h(2)=2，走到这里无法走到4号结点，因为没有邻接边，3号结点不近没有邻接边，而且高度也不满足条件，也不能走到1号结点，怎么办呢？

可以用重贴标签的方法。当前结点无法前进时，令当前结点的高度=所有邻接点高度的最小值+1；如果没有邻接边，则令当前结点的高度=结点数；退回一步，重新搜索。

算法设计

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

算法实现

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;
        }
}

算法复杂度分析
时间复杂度：找到一条可增广路时间为O(V)，最多会执行O(VE)次，因为关键边的总数为O(VE)，因此总的时间复杂度为O(V²E)，其中V为结点个数，E为边的数量。

空间复杂度O(V)。

最小费用路算法——最小费用最大流

问题分析

除了流量之外，还定义了一个单位流量的费用。对于网络上的一个流flow，其费用为

$\cos t(flow)=\sum\limits_{<x,y>\in E}{\cos t(x,y)*flow(x,y)}$

网络流的费用=单位流量费用*每条边的流量

算法设计

有两种思路：
1. 先找最小费用路，在该路径上增流，增加到最大流，称为最小费用路算法。
2. 先找最大流，然后找负费用圈，消减费用，减少到最小费用，称为消圈算法。
最小费用路算法，是在残余网络上寻找从源点到汇点的最小费用路，即从源点到汇点的以单位费用为权的最短路，然后沿着最小费用路增流，直到找不到最小费用路为止。

算法解释

创建混合网络。先初始化为零流，零流对应混合网络中，正向边容量为cap，流量为0，费用为cost，反向边容量为0，流量为0，费用为-cost。
找最小费用路。先初始化每个结点的距离为无穷大，然后令源点的距离dist[v₁]=0。在混合网络中，从源点出发，沿可行边（E[i].cap>E[i].flow）广度搜索每个邻接点，如果当前距离dist[v]>dist[u]+E[i].cost，则更新为最短距离：dist[v]=dist[u]+E[i].cost，并记录前驱。根据前驱数组，找到一条最短费用路，增广路经：1-2-5-6。
然后沿着增广路经正向增流d，反向减流d。从汇点逆向找最小可增流量d=min(d,E[i].cap-E[i].flow)，增流量d=3，产生费用为mincost+=dist[v₆]d=83=24。
找最小费用路。先初始化每个结点距离为无穷大，然后令源点的距离dist[v₁]=0。在混合网络中，从源点出发，沿可行边（E[i].cap>E[i].flow）广度搜索每个邻接点，如果当前距离dist[v]>dist[u]+E[i].cost，则更新为最短距离：dist[v]=dist[u]+E[i].cost，并记录前驱。根据前驱数组，找到一条最短费用路，增广路经：1-3-4-6。
然后沿着增广路经正向增流d，反向减流d。从汇点逆向找最小可增流量d=min(d,E[i].cap-E[i].flow)，增流量d=4，产生费用为mincost+=24+dist[v₆]d=24+164=88。
找最小费用路。先初始化每个结点距离为无穷大，然后令源点的距离dist[v₁]=0。在混合网络中，从源点出发，沿可行边（E[i].cap>E[i].flow）广度搜索每个邻接点，发现从源点出发已经没有可行边，结束，得到的网络流就是最小费用最大流。把混合网络中flow>0的边输出，就是我们要的实流网络。

代码实现

（1）定义结构体。结构体的定义与ISAP中结构体相同，边只是多了一个cost域，fisrt指向第一个邻接边，next是吓一跳邻接边，该结构体用于创建邻接表。

   struct Vertex
{
   int first;
}V[N];
struct Edge
{
   int v, next;
   int cap, flow,cost;
}E[M];

（2）创建残余网络边。正向边的容量为cap，流量为0，费用为cost，反向边容量为0，流量为0，费用为-cost。

void add_edge(int u, int v, int c,int cost)
{
    E[top].v = v;
    E[top].cap = c;
    E[top].flow = 0;
    E[top].cost = cost;
    E[top].next = V[u].first;
    V[u].first = top++;
}
void add(int u,int v, int c,int cost)
{
    add_edge(u,v,c,cost);
    add_edge(v,u,0,-cost);
}

（3）求最小费用路。先初始化每个结点距离无穷大，然后令源点的距离dist[v₁]=0。在混合网络中，从源点出发，沿可行边（E[i].cap>E[i].flow）广度搜索每个邻接点，如果当前距离dist[v]>dist[u]+E[i].cost，则更新为最短距离：dist[v]=dist[u]+E[i].cost，并记录前驱。

bool SPFA(int s, int t, int n)//求最短费用路的SPFA
{
    int i, u, v;
    queue <int> qu; // 队列，STL实现
    memset(vis,false,sizeof(vis));//访问标记初始化
    memset(c,0,sizeof(c));   //入队次数初始化
    memset(pre,-1,sizeof(pre)); //前驱初始化
    for(i=1;i<=n;i++)
    {
        dist[i]=INF; //距离初始化
    }
    vis[s]=true; //顶点入队vis要做标记
    c[s]++;     //要统计顶点的入队次数
    dist[s]=0;
    qu.push(s);
    while(!qu.empty())
    {
        u=qu.front();
        qu.pop();
        vis[u]=false;
        //队头元素出队，并且消除标记
        for(i=V[u].first; i!=-1; i=E[i].next)//遍历顶点u的邻接表
        {
            v=E[i].v;
            if(E[i].cap>E[i].flow && dist[v]>dist[u]+E[i].cost)//松弛操作
            {
                dist[v]=dist[u]+E[i].cost;
                pre[v]=i; //记录前驱
                if(!vis[v]) //顶点v不在队内
                {
                    c[v]++;
                    qu.push(v);   //入队
                    vis[v]=true; //标记
                    if(c[v]>n) //超过入队上限，说明有负环
                        return false;
                }
            }
        }
    }
    cout<<"最短路数组"<<endl;
    cout<<"dist[ ]=";
    for(int i=1;i<=n;i++)
       cout<<"  "<<dist[i];
    cout<<endl;
    if(dist[t]==INF)
        return false; //如果距离为INF，说明无法到达，返回false
    return true;
}

（4）沿着最小费用路增流。从汇点逆向找最小可增流量d=min(d,E[i].cap-E[i].flow)。沿着增广路径正向边增流d，反向边减流d，产生费用为mincost+=dist[t]*d。

int MCMF(int s,int t,int n) //minCostMaxFlow
{
    int d; //可增流量
    int i,mincost;//maxflow 当前最大流量，mincost当前最小费用
    mincost=0;
    while(SPFA(s,t,n))//表示找到了从s到t的最短路
    {
        d=INF;
        cout<<endl;
        cout<<"增广路径："<<t;
        for(i=pre[t]; i!=-1; i=pre[E[i^1].v])
        {
            d=min(d, E[i].cap-E[i].flow); //找最小可增流量
            cout<<"--"<<E[i^1].v;
        }
        cout<<"增流："<<d<<endl;
        cout<<endl;
        maxflow+=d; //更新最大流
        for(i=pre[t]; i!=-1; i=pre[E[i^1].v])//修改残余网络，增加增广路上相应弧的容量，并减少其反向边容量
        {
            E[i].flow+=d;
            E[i^1].flow-=d;
        }
        mincost+=dist[t]*d; //dist[t]为该路径上单位流量费用之和 ，最小费用更新
   }
    return mincost;
}

复杂度分析

时间复杂度：找到一条可增广路时间为O(E)，最多会执行O(VE)次，因为关键边的总数为O(VE)，因此总的时间复杂度为O(VE²)，其中V为结点个数，E为边的数量。
空间复杂度：O(V)。

消圈算法

算法设计
三个过程：

找给定网络的最大流。
在最大流对应的混合网络找负费用圈。
消负费用圈：负费用圈同方向的边流量加d，反方向的边流量减d。d为负费用圈所有边的最小可增量cap-flow。

算法的核心是在残余网络中找负费用圈。

算法解释

求最大流。用最大流求解算法求解最大流。
在最大流对应的混合网络中找负费用圈。在最大流的混合网络中，沿着cap>flow的边找负费用圈，就是各边费用之和为负的圈。
负费用圈同方向的边流量加d，反方向的边流量减d。沿找到的负费用全增流，其增量为组成负费用圈的所有边的最小可增量cap-flow。负费用圈说明费用较高，可以对费用为负的边减流，因为该残余网络为特殊的残余网络，负费用的边流量也是负值，减流实际上需要加上增流量d，为了维持平衡性，负费用圈同方向的边流量加d，反方向的边流量减d。
在混合网络中继续找负费用圈。在混合网络中，沿着cap>flow的边找负费用圈，已经找不到负费用圈，算法结束。把混合网络中flow>0的边输出，就是我们需要的实流网络。

复杂度分析

时间复杂度：最大流方法为O(V²E)，如果每次消去负费用圈至少使费用下降一个单位，最多执行ECM此找负费用圈和增减流操作（C为每条边费用上界，M为每条边容量上界）。该算法时间复杂度为O(V²E²CM)。
空间复杂度O(V)。