【学习笔记】网络流问题

为了更好地~~装逼~~学习OI知识，我最近去学习了一下网络流的相关知识 于是我决定今天在这里~~装个逼~~浅谈一下网络流问题 ~~卖弄一下自己的学识~~以便大家更好地理解图论中的网络流 不过在这之前，还是先说一下网络流问题是啥吧 ## 1.什么是网络流问题 先来水一波定义：   因此很容易知道所谓的网络最大流就是最大的可行流 以下就是一个求网络最大流的栗子：   图中的浅蓝色数字，是实际走的流量，并且构成源点到终点的最大流量。 源节点1到节点4为什么不是7？ 因为从节点4流出的水流，加起来才5！ 换句话说，到节点4就流不过去这么多了。 至于为何是4，而不是5，同样道理，因为节点3到节点6的容量有限制！ 分析到这里大家可能发现了，即使不按照图中浅蓝色数字分配，也可以找到其他水流分配路径，使最大水流量达到10。但没有比10更高的了。 而网络最小割就是从图G(V,E)中去除一些边，使得图G中源点S到终点T不连通。如果去除的这些边的权和最小，就是最小割。而这个权和可以证明等于网络的最大流量！（很明显在上图中，如果切除边2->5、4->5、3->6，就是一个最小割，三条边的权和为10=最大流量10。） #### 因此，求网络最大流的问题就可以转换成求网络最小割的问题！ ## 2.网络最小割算法Stoer-Wagner 如果要求一个无向连通图中的网络最小割，我们可能会首先想到这种思路： 使用最小切割最大流定理： 1.初始化min=MAXINT,确定一个源点 2.枚举汇点 3.计算最大流，并确定当前源汇的最小割集，若比min小更新min 4.转到2直到枚举完毕 5.min即为所求输出min ~~（看不懂很正常，也不用去费劲理解，因为下面还有更好的算法）~~ 但是这种思路复杂度很高：枚举汇点要O(n)，最短增广路最大流算法求最大流是O((n^2)m)复杂度，在复杂网络中O(m)=O(n^2)，算法总复杂度就是O(n^5)；哪怕采用最高标号预进流算法求最大流O((n^2)(m^0.5))，算法总复杂度也要O(n^4) 所以用网络流算法求解最小割集复杂度不会低于O(n^4)。 ##### 因此，为了解决以上问题，就有了Stoer-Wagner算法： 1.初始化min=MAXINT，固定一个顶点P 2.从点P用“类似”prim的算法扩展出“最大生成树”，记录最后扩展的顶点和最后扩展的边 3.计算最后扩展到的顶点的切割值（即与此顶点相连的所有边权和），若比min小更新min 4.合并最后扩展的那条边的两个端点为一个顶点（当然他们的边也要合并） 5.转到第2步，合并N-1次后结束 6.min即为所求，输出min prim本身复杂度是O(n^2)，合并n-1次，算法复杂度即为O(n^3)，如果在prim中加堆优化，复杂度会降为O((n^2)logn) 原理：考虑任意两个点为s，t，如果全局最小割中s，t不在一个集合中，那么显然全局最小割即为s-t最小割。否则我们将s，t缩成一个节点对于答案是没有影响的。基于这一点，每次将问题规模减小后求解。一开始选择的节点是作为s-t的中间节点集，因为每次扩展是选取联系度最大的点扩展，所以中间节点集中点互相间的联系度是大于st到中间点集的联系度的，而最后加入的点t的联系度是最小的，所以最小割即为这个点的联系度，即为s通过中间节点集到t的流量加上s直接到t的流量。所以就证明了每次拓展求出的是s-t的最小割。 好的，废话不多说~~（因为已经说够了）~~，下面贴~~高清无码的~~测试程序： ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAX_N 500 #define INF 0x3f3f3f3f int G[MAX_N][MAX_N]; int v[MAX_N]; // v[i]代表节点i合并到的顶点 int w[MAX_N]; // 定义w(A,x) = ∑w(v[i],x)，v[i]∈A,即为与点i相连的边的边权之和 bool vis[MAX_N]; // 用来标记是否该点加入了A集合 int squ[MAX_N]; //记录移除的节点次序 int index; int stoer_wagner(int n) { int min_cut = INF; int r=0; for (int i = 0; i < n; ++i) { v[i] = i; // 初始还未合并，都代表节点本身 } while (n > 1) { int pre = 0; // pre用来表示之前加入A集合的点（在t之前一个加进去的点） memset(vis, 0, sizeof(vis)); memset(w, 0, sizeof(w)); for (int i = 1; i < n; ++i) //求出 某一轮最大生成树的最后两个节点，并且去除最后的t，将与t连接的边归并 { int k = -1; for (int j = 1; j < n; ++j) // 选取V-A中的w(A,x)最大的点x加入集合 { if (!vis[v[j]]) { w[v[j]] += G[v[pre]][v[j]]; if (k == -1 || w[v[k]] < w[v[j]]) { k = j; } } } vis[v[k]] = true; // 标记该点x已经加入A集合 if (i == n - 1) // 若|A|=|V|（所有点都加入了A），结束 { const int s = v[pre], t = v[k]; // 令倒数第二个加入A的点（v[pre]）为s，最后一个加入A的点（v[k]）为t cout<<t<<"--->"<<s<<endl; squ[r++]=t; if(w[t]<min_cut) { min_cut=w[t]; // index=r; } //min_cut = min(min_cut, w[t]); // 则s-t最小割为w(A,t)，用其更新min_cut for (int j = 0; j < n; ++j) // Contract(s,t) { G[s][v[j]] += G[v[j]][t]; G[v[j]][s] += G[v[j]][t]; } v[k] = v[--n]; // 删除最后一个点（即删除t,即将t合并到s） } // else 继续 pre = k; } } return min_cut; } int main() { int n, m; scanf("%d%d", &n, &m); memset(G, 0, sizeof(G)); for(int i=1;i<=m;i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); G[u][v] += w; G[v][u] += w; } int z=n; //printf("%d\n", stoer_wagner(n)); cout<<"\n归并的步骤为："<<endl; int res=stoer_wagner(n); cout<<"\n最小割的总权值为： "<<res<<"\n图划分为部分A："; //cout<<"图划分为部分A："; for(int i=0;i<z;i++) { if(i==index) cout<<"部分B："; cout<<squ[i]<<" "; } return 0; } ``` ~~把测试帮助理解的测试输出删了就是标程了~~ ## 3.网络最大流算法Dinic #### 本版块的讲解部分援引了SYCstudio巨佬的博客 [地址](https://www.cnblogs.com/SYCstudio/p/7260613.html) ----------------------------------------- 讲解前再来补一波定义 容量：一条边上可供流过的最大流量 残量：一条边上的容量-流量 ----------------------------------------- 网络流的所有算法都是基于一种增广路的思想，下面首先简要地说一下增广路思想，其基本步骤如下： 1.找到一条从源点到汇点的路径，使得路径上任意一条边的残量>0（注意是小于而不是小于等于，这意味着这条边还可以分配流量），这条路径便称为增广路 2.找到这条路径上最小的F[u][v]（我们设F[u][v]表示u->v这条边上的残量即剩余流量），下面记为flow 3.将这条路径上的每一条有向边u->v的残量减去flow，同时对于起反向边v->u的残量加上flow（为什么呢？我们下面再讲） 4.重复上述过程，直到找不出增广路，此时我们就找到了最大流 这个算法是基于增广路定理(Augmenting Path Theorem): 网络达到最大流当且仅当残留网络中没有增广路（由于我知识水平不高，暂且不会证明） 比如这个栗子： [](https://imgchr.com/i/ksbFRU) --------------------------------------- 我们知道，当我们在寻找增广路的时候，在前面找出的不一定是最优解，如果我们在减去残量网络中正向边的同时将相对应的反向边加上对应的值，我们就相当于可以反悔从这条边流过。 比如说我们现在选择从u流向v一些流量，但是我们后面发现，如果有另外的流量从p流向v，而原来u流过来的流量可以从u->q流走，这样就可以增加总流量，其效果就相当于p->v->u->q，用图表示就是：  图中的蓝色边就是我们首次增广时选择的流量方案，而实际上如果是橘色边的话情况会更优，那么我们可以在v->u之间连一条边容量为u->v减去的容量，那我们在增广p->v->u->q的时候就相当于走了v->u这条"边"，而u->v的流量就与v->u的流量相抵消，就成了中间那幅图的样子了。 如果是v->u时的流量不能完全抵消u->v的，那就说明u还可以流一部分流量到v，再从v流出，这样也是允许的。 反向边的实现可以用邻接表，我们把边从0开始编号，每加入一条原图中的边u->v时，加入边v->u流量设为0，那么这时对于编号为i的边u->v，我们就可以知道i^1就是其反向边v->u。 ---------------------------------------- 虽然说我们已经知道了增广路的实现，但是单纯地这样选择可能会陷入不好的境地，比如说这个经典的例子：  我们一眼可以看出最大流是999(s->v->t)+999(s->u->t) 但如果程序采取了不恰当的增广策略：s->v->u->t  我们发现中间会加一条u->v的边  而下一次增广时：  若选择了s->u->v->t  然后就变成  这是个非常低效的过程，并且当图中的999变成更大的数时，这个劣势还会更加明显。 怎么办呢？ 这时我们引入Dinic算法 ---------------------------- 为了解决我们上面遇到的低效方法，Dinic算法引入了一个叫做分层图的概念。 具体就是对于每一个点，我们根据从源点开始的bfs序列，为每一个点分配一个深度，然后我们进行若干遍dfs寻找增广路，每一次由u推出v必须保证v的深度必须是u的深度+1。下面给出代码： ```cpp #include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<cstring> #define inf 2147400000 using namespace std; int cnt=1;//这里的cnt赋值必须为1,因为下面用的是i^1来找与其对应的相反边 int head[505]; int n,m,S,T; int cur[505];//cur就是记录当前点u循环到了哪一条边 int dep[505];//分层图中标记深度 struct Edge//前向星建边 { int nst,dis,to; }edge[5000]; void add(int u,int v,int c) { edge[++cnt].nst=head[u]; edge[cnt].to=v; edge[cnt].dis=c; head[u]=cnt; } bool bfs() { queue <int> q;//定义一个bfs寻找分层图时的队列 memset(dep,0,sizeof(dep)); q.push(S); dep[S]=1;//源点深度为1 while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=edge[i].nst) { int v=edge[i].to; if((!dep[v]) && (edge[i].dis!=0))//若该残量不为0，且V[i]还未分配深度，则给其分配深度并放入队列 { dep[v]=dep[u]+1; q.push(v); } } } return dep[T];//当汇点的深度不存在时，说明不存在分层图，同时也说明不存在增广路 } int dfs(int u,int flow)//u是当前节点，flow是当前流量 { if(u==T) return flow;//当已经到达汇点，直接返回 for(int i=cur[u];i;i=edge[i].nst) { cur[u]=i;//一定要在i增加的同时改变cur[u]的值，以达到记录当前弧的目的 int v=edge[i].to; if((dep[v]==dep[u]+1) && (edge[i].dis!=0))//注意这里要满足分层图和残量不为0两个条件 { int fl=dfs(v,min(flow,edge[i].dis));//向下增广 if(fl)//若增广成功 { edge[i].dis-=fl;//正向减边 edge[i^1].dis+=fl;//反向加边 return fl;//向上传递 } } } return 0;//否则说明没有增广路，返回 } int Dinic() { int ans=0;//记录最大流量 while(bfs()) { memcpy(cur,head,sizeof(head));//每一次建立完分层图后都要把cur置为每一个点的第一条边 ans+=dfs(S,inf); } return ans; } int main() { scanf("%d%d%d%d",&n,&m,&S,&T); int x,y,z; for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,0);//反向建边 } printf("%d\n",Dinic()); return 0; } ``` ## 4.最小费用最大流算法EK EK算法，即spfa+增广路~~（没错就是那个死掉的spfa）~~ 之所以不能用dijkstra，是因为万一图里有负边权就凉凉了~~（当然，如果你能把图魔改成全是正边权的图也可以跑dijkstra，但是我太弱了，做不到）~~ 在图上 以费用为边权 跑spfa：在更新的过程中，如果更新成功，那么就往下一个结点尽可能多地流水，并且把流水的路径记录下来（pre[v]=u）。 跑完SPFA后，顺着之前记录的路径从汇点溯回到源点，同时寻找增广路。 最小的总费用就是 (当前路径所流总量) * (s到t的最短路径) 的和 下面来贴~~高清无码的~~标程： ```cpp #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #define inf 0x3f3f3f3f using namespace std; int cnt=1,n,m,s,t,mcost,mflow; int head[5005],pre[5005]; int dis[5005];//dis为从S到这个点的最小总费用 int flow[5005];//flow为从S到这个点的最大可更新流量 bool vis[5005];//vis为这个点有没有被标记过(废话) struct Edge { int to,nst,dis,flow;//dis是费用，flow是流量 }edge[100005]; void add(int a,int b,int c,int d) { edge[++cnt].nst=head[a]; edge[cnt].to=b; edge[cnt].flow=c;//输入的时候仔细看一看 edge[cnt].dis=d;//要是把费用和流量搞反了就凉了 head[a]=cnt; } bool spfa() { queue <int> q; memset(vis,0,sizeof(vis)); memset(dis,inf,sizeof(dis)); dis[s]=0; vis[s]=1; flow[s]=inf; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i;i=edge[i].nst) { int v=edge[i].to; if(edge[i].flow&&dis[u]+edge[i].dis<dis[v])//如果边还有流量就尝试更新 { dis[v]=edge[i].dis+dis[u];//更新最短路径 flow[v]=min(flow[u],edge[i].flow);//到达v点的水量取决于边剩余的容量和u点的水量 pre[v]=i;//记录路径 if(!vis[v]) { vis[v]=1; q.push(v); } } } } return dis[t]!=inf;//如果还能跑到终点，就说明还不是最大流，还要继续跑spfa } void update() { int x=t; while(x!=s) { int i=pre[x]; edge[i].flow-=flow[t]; edge[i^1].flow+=flow[t]; x=edge[i^1].to;//沿着记录下的路径寻找增广路 } mflow+=flow[t];//累计流量 mcost+=flow[t]*dis[t];//累计费用 } void EK(int s,int t) { while(spfa())//当还有多余流量时 update(); } int main() { scanf("%d%d%d%d",&n,&m,&s,&t); int a,b,c,d; for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&a,&b,&c,&d); add(a,b,c,d); add(b,a,0,-d);//依旧不要忘记反向建边 } EK(s,t); printf("%d %d\n",mflow,mcost); return 0; } ``` ## 5.究极最大流算法ISAP 其实Dinic已经足够高效了，但那些~~（闲着没事干）~~的计算机科学家们对Dinic的效率仍不满足，于是就有了ISAP算法。 在Dinic中我们每次增广前都进行了一次bfs来初始化每个点的深度，虽然一次标号增广了很多条路，但是我们还是很有可能要跑很多遍bfs导致效率不高。 那有没有什么办法只跑一次bfs呢? 那就是ISAP算法了！ ----- ### ISAP的运行过程： 1. 从t到s跑一遍bfs，标记深度（为什么是从t到s呢？后面会讲） 2. 从s到t跑dfs，和Dinic类似，只是当一个点跑完后，如果从上一个点传过来的flow比该点的used大（对于该点当前的深度来说，该点在该点以后的路上已经废了），则把它的深度加1，如果出现断层（某个深度没有点），结束算法 3. 如果操作2没有结束算法，重复操作2 ----- ISAP其实与Dinic差不多，但是它只跑一遍bfs，但是每个点的层数随着dfs的进行而不断提高（这样就不用反复跑bfs重新分层了），当s的深度大于n时（这就是为什么bfs要从t到s），结束算法。 例程（自带当前弧优化）: ```cpp #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> using namespace std; const int inf=1<<30; int cnt=1,head[13000],cur[13000]; int n,m,s,t; struct Edge{ int to; int nst; int dis; }edge[250000]; inline void add(int a,int b,int b) { edge[++cnt].nst=head[a]; edge[cnt].to=b; edge[cnt].dis=c; head[a]=cnt; } int dep[13000];//表示每个点i的深度 int gap[13000];//表示深度为i的点有几个 void bfs()//从t到s遍历，标记每个点的深度 { memset(dep,-1,sizeof(dep));//初始化dep数组为-1 memset(gap,0,sizeof(gap)); dep[t]=0;//初始化t点的深度为0 gap[0]=1;//初始化深度为0的点有1个 queue<int>q; q.push(t); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i;i=edge[i].nst) { int v=edge[i].to; if(dep[v]!=-1)continue;//防止反复修改某一个点 q.push(v); dep[v]=dep[u]+1; gap[dep[v]]++; } } return; } int maxflow; int dfs(int u,int flow)//从s到t进行dfs { if(u==t) { maxflow+=flow; return flow; } int used=0; for(int i=cur[u];i;i=edge[i].nst) { cur[u]=i;//在i增加的同时修改cur[u]以记录当前弧 int d=edge[i].to; if(edge[i].dis&&dep[d]+1==dep[u]) { int mi=dfs(d,min(edge[i].dis,flow-used)); if(mi) { edge[i].dis-=mi; edge[i^1].dis+=mi; used+=mi; } if(used==flow)return used; } } //上半部分几乎和Dinic相同 //如果已经到了这里，说明该点出去的所有点都已经流过了 //并且从前面点传过来的流量还有剩余，则此时，要对该点更改dep //使得该点与该点出去的点分隔开 --gap[dep[u]]; if(gap[dep[u]]==0)dep[s]=n+1;//如果出现了断层，就把终点的层++ dep[u]++;//层++ gap[dep[u]]++;//层对应的个数++ return used; } int ISAP() { maxflow=0; bfs(); while(dep[s]<n) { memcpy(cur,head,sizeof(head)); dfs(s,inf); } return maxflow; } int main(){ int i=1; scanf("%d%d%d%d",&n,&m,&s,&t); int u,v,w; for(i=1;i<=m;i++)scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,0); printf("%d",ISAP()); return 0; } ```