优化扩展——重贴标签算法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)。