算法笔记之线性规划网络流问题（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步。
- 算法结束，已经找到最大流。
算法实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 |
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. 先找最大流，然后找负费用圈，消减费用，减少到最小费用，称为消圈算法。
最小费用路算法，是在残余网络上寻找从源点到汇点的最小费用路，即从源点到汇点的以单位费用为权的最短路，然后沿着最小费用路增流，直到找不到最小费用路为止。
算法解释
- 创建混合网络。先初始化为零流，零流对应混合网络中，正向边容量为cap，流量为0，费用为cost，反向边容量为0，流量为0，费用为-cost。
- 找最小费用路。先初始化每个结点的距离为无穷大，然后令源点的距离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。
- 然后沿着增广路经正向增流d，反向减流d。从汇点逆向找最小可增流量d=min(d,E[i].cap-E[i].flow)，增流量d=3，产生费用为mincost+=dist[v6]d=83=24。
- 找最小费用路。先初始化每个结点距离为无穷大，然后令源点的距离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。
- 然后沿着增广路经正向增流d，反向减流d。从汇点逆向找最小可增流量d=min(d,E[i].cap-E[i].flow)，增流量d=4，产生费用为mincost+=24+dist[v6]d=24+164=88。
- 找最小费用路。先初始化每个结点距离为无穷大，然后令源点的距离dist[v1]=0。在混合网络中，从源点出发，沿可行边（E[i].cap>E[i].flow）广度搜索每个邻接点，发现从源点出发已经没有可行边，结束，得到的网络流就是最小费用最大流。把混合网络中flow>0的边输出，就是我们要的实流网络。
代码实现
（1）定义结构体。结构体的定义与ISAP中结构体相同，边只是多了一个cost域，fisrt指向第一个邻接边，next是吓一跳邻接边，该结构体用于创建邻接表。
|
1 2 3 4 5 6 7 8 9 10 |
struct Vertex { int first; }V[N]; struct Edge { int v, next; int cap, flow,cost; }E[M]; |
（2）创建残余网络边。正向边的容量为cap，流量为0，费用为cost，反向边容量为0，流量为0，费用为-cost。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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，并记录前驱。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
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。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
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(VE2)，其中V为结点个数，E为边的数量。
- 空间复杂度：O(V)。
消圈算法
算法设计
三个过程：
- 找给定网络的最大流。
- 在最大流对应的混合网络找负费用圈。
- 消负费用圈：负费用圈同方向的边流量加d，反方向的边流量减d。d为负费用圈所有边的最小可增量cap-flow。
算法的核心是在残余网络中找负费用圈。
算法解释
- 求最大流。用最大流求解算法求解最大流。
- 在最大流对应的混合网络中找负费用圈。在最大流的混合网络中，沿着cap>flow的边找负费用圈，就是各边费用之和为负的圈。
- 负费用圈同方向的边流量加d，反方向的边流量减d。沿找到的负费用全增流，其增量为组成负费用圈的所有边的最小可增量cap-flow。负费用圈说明费用较高，可以对费用为负的边减流，因为该残余网络为特殊的残余网络，负费用的边流量也是负值，减流实际上需要加上增流量d，为了维持平衡性，负费用圈同方向的边流量加d，反方向的边流量减d。
- 在混合网络中继续找负费用圈。在混合网络中，沿着cap>flow的边找负费用圈，已经找不到负费用圈，算法结束。把混合网络中flow>0的边输出，就是我们需要的实流网络。
复杂度分析
- 时间复杂度：最大流方法为O(V2E)，如果每次消去负费用圈至少使费用下降一个单位，最多执行ECM此找负费用圈和增减流操作（C为每条边费用上界，M为每条边容量上界）。该算法时间复杂度为O(V2E2CM)。
- 空间复杂度O(V)。
![[leetcode]populating next right pointers in each node](http://www.yushuai.xyz/wp-content/themes/MyDream/timthumb.php?src=https://dqhplhzz2008-1251830035.cos.ap-guangzhou.myqcloud.com/wp-content/uploads/2019/04/pnrpien1.png&h=180&w=300&zc=1)
![[leetcode]题目解析（190524）](http://www.yushuai.xyz/wp-content/themes/MyDream/timthumb.php?src=http://tech.yushuai.xyz/wzpt/largestrectangle.png&h=180&w=300&zc=1)
![[Leetcode]merge sorted array](http://www.yushuai.xyz/wp-content/themes/MyDream/img/random/21.jpg)
