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