算法笔记之线性规划网络流问题(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;如果没有邻接边,则令当前结点的高度=结点数;退回一步,重新搜索。

算法设计

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

算法实现

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(V2E),其中V为结点个数,E为边的数量。

空间复杂度O(V)。

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

问题分析

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

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

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

算法设计

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

算法解释

  1. 创建混合网络。先初始化为零流,零流对应混合网络中,正向边容量为cap,流量为0,费用为cost,反向边容量为0,流量为0,费用为-cost。
  2. 找最小费用路。先初始化每个结点的距离为无穷大,然后令源点的距离dist[v1]=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
  3. 然后沿着增广路经正向增流d,反向减流d。从汇点逆向找最小可增流量d=min(d,E[i].cap-E[i].flow),增流量d=3,产生费用为mincost+=dist[v6]d=83=24。
  4. 找最小费用路。先初始化每个结点距离为无穷大,然后令源点的距离dist[v1]=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
  5. 然后沿着增广路经正向增流d,反向减流d。从汇点逆向找最小可增流量d=min(d,E[i].cap-E[i].flow),增流量d=4,产生费用为mincost+=24+dist[v6]d=24+164=88。
  6. 找最小费用路。先初始化每个结点距离为无穷大,然后令源点的距离dist[v1]=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[v1]=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;
}

复杂度分析

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

消圈算法

算法设计
三个过程:

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

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

算法解释

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

复杂度分析

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

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注