【网络流】EK Dinic 算法
【网络流】EK Dinic 算法
这两天学习了网络流，故写点东西加深理解。
关于网络流定义证明之类，前人之述备矣，此处整理一些比较舒适的代码实现。
EK全名是 Edmonds-Karp.
慢但是码量少一些，让人十分欢乐。
EK不需要两次搜索也不需要分层。
更欢乐的是能用EK过的数据范围都较小。这是因为算法的时间复杂度 \(O(VE^2)\) 决定了数据上界。因此存图使用邻接矩阵就行了。
例题P2472 【SCOI2007】 蜥蜴
思路：此题关键在于建图。因为每一个点有容量限制，难以维护，我们不妨把点转化为边，一个入点一个出点，其中连线即为“点的容量”，入边接入点，出边接出点。
因此建图为：
连接源点 \(S\) 和所有有蜥蜴的柱子的入点，容量为1（因为只有一只蜥蜴）；连接所有柱子的格子的入点和出点，容量为柱子的高度；连接所有蜥蜴可以跳过的柱子的入点和出点，容量为 \(\inf\) ;连接所有可以跳到边界外的柱子的出点到 \(T\)，容量仍然是\(\inf\).读者如果仔细思考以上的连法的实际意义便可以很快理解。很多网络流题目考察的就是将复杂的题目要求抽象成图并建立模型的能力。
#include iostream#include cstring#include queueusing namespace std;int map[22][22];int lzd[22][22];int r[1000][1000];int n,m,s,t,ct;int d;int pre[1000];//用以存储增广路int vis[1000];int BFS(){ memset(pre,0,sizeof(pre)); memset(vis,0,sizeof(vis)); queueint q; vis[s]=1; pre[s]=s; q.push(s); while(q.size()) { int u=q.front(); q.pop(); for(int v = 1; v = t; v++) { if(r[u][v]0!vis[v])//与Dinic同理，如果尚有残量且没去过 { vis[v]=1; pre[v]=u; if(v==t)return 1;//找到了汇点，这是一条增广路，结束 q.push(v); } } } return 0;}int EK(){ int ans, d; ans=0; while(BFS()) { d=1145141919; for(int i = t; i != s; i = pre[i]) { d=min(d,r[pre[i]][i]);//找到这条增广路的“瓶颈”即最小容量，即这条增广路对总流量的贡献 } for(int i = t; i != s; i = pre[i]) { //给增广路上所有边和反边更新残量 r[pre[i]][i]-=d; r[i][pre[i]]+=d; } ans+=d; } return ans;}int main(){ cin n m d; cin.get();cin.get(); for(int i = 1; i=n;i++) { for(int j = 1; j = m; j++) { char tmp=cin.get(); map[i][j]=tmp-'0'; } cin.get();cin.get(); } for(int i = 1; i=n;i++) { for(int j = 1; j = m; j++) { char tmp=cin.get(); lzd[i][j]=(tmp=='.')?0:1; if(lzd[i][j])ct++; } cin.get();cin.get(); }//输入真恶心，要cin.get()两遍才能吃掉回车符，天啊 //以下建图思路如上，顺序可能不同。 //超级源点下标当然是1啊（各种方便反正） //对于所有柱子，入点的下标为1+(i-1)*m+j, 如果你从左往右从上往下一个个数格子的话那么这就是编号+1。出点的下标为1+(i-1)*m+j+m*n,正好加上一个图的面积。 //超级汇点直接2*m*n+2，即超级源点+两个面积（出入点）+1 s=1; t=2+n*m*2; for(int i = 1; i=n;i++) { for(int j = 1; j = m; j++) { if(lzd[i][j])r[s][1+(i-1)*m+j]=1; } } for(int i = 1; i=n;i++) { for(int j = 1; j = m; j++) { r[1+(i-1)*m+j][1+(i-1)*m+n*m+j]=map[i][j]; } } for(int i = 1; i=n;i++) { for(int j = 1; j = m; j++) { if(map[i][j]) if(j=d||j=m+1-d||i=d||i=n+1-d) r[1+(i-1)*m+m*n+j][t]=1145141919; } } for(int i1 = 1; i1=n;i1++) { for(int j1 = 1; j1 = m; j1++) { for(int i2 = 1; i2=n;i2++) { for(int j2 = 1; j2 = m; j2++) { if(i1==i2j1==j2)continue;//一样的话就没必要连上了 if((i1-i2)*(i1-i2)+(j1-j2)*(j1-j2)=d*d)//省去开方的一种毕达哥拉斯定理优化形式，实在是太方便了啊 { r[1+n*m+(i2-1)*m+j2][1+(i1-1)*m+j1]=1145141919; r[1+n*m+(i1-1)*m+j1][1+(i2-1)*m+j2]=1145141919; } } } } } cout ct-EK();//输出不能逃出的，所以记得要用ct减去最大流量啊}这个算法原本是叫做 Dinitz 的，但是由于 Shimon Even 教授的口误，长期以 Dinic 的名字流传。
比起 EK 在稠密图上快一些,时间复杂度 \(O(V^2 E)\). 适用范围可能更广。
例题P3376 【模板】网络最大流
#include iostream#include cstring#include queueusing namespace std;int n,m,s,t,tot;struct edge{ int b; int next; long long w;}e[11000];//有反向边，所以一定要两倍开数组啊int head[210];void add(int a, int b, long long w){ e[++tot].b=b; e[tot].next=head[a]; e[tot].w=w; head[a]=tot;}//普通的前向星int d[210];int cur[210];//当前弧优化int BFS(){ memset(d,0,sizeof(d)); memset(cur,0,sizeof(cur)); queueint q; q.push(s); d[s]=1; cur[s]=head[s]; while(q.size()) { int u=q.front();q.pop(); int v; long long w;//不开longlong见祖宗 for(int i = head[u]; i; i=e[i].next) { v=e[i].b; w=e[i].w; if(d[v]==0w0)//d[v]=0时说明未被访问过，此时充当类似vis[]作用 { q.push(v); d[v]=d[u]+1;//向前更新 cur[v]=head[v];//初始化 } } } if(d[t]==0)return 0;//说明d[t]未被访问，找不到增广路了 else return 1;}long long DFS(int u, long long r){ int v; if(u==t)return r; for(int i = cur[u]; i; i=e[i].next)//当前弧优化，再次dfs到此时就可以知道上次完成了哪些分支的dfs并清除了其残量 { cur[u]=i; int v=e[i].b; long long w=e[i].w; if((d[v]==d[u]+1)w!=0)//确认v在下一层并且有残量 { long long rr=DFS(v,min(r,w)); if(rr0) { e[i].w-=rr; e[i^1].w+=rr; return rr; } } } return 0;}long long DINIC(){ long long ans=0; while(BFS()) { while(long long d=DFS(s,1145141919810))ans+=d;//'='号返回赋值的内容,可以顺便放进while()里面 } return ans;}int main(){ cin n m s t; tot=1;//重要。解释见下。 for(int i = 1; i = m; i++) { int u ,v; long long w; cin u v w; add(u,v,w); add(v,u,0);//建反边。反边的容量是0而不是-w，这在一些情况下可以输出正确结果（？）但是另一些情况下会死循环。 //因为开始tot=1, 所以开始的一些正反边对下标为(2,3),(4,5)等，正好可以按位异或1相互得到。 } cout DINIC();}解释1：为了在代码实现中方便地得到反边(使用链式前向星时)，由按位异或的性质可以快速得到反边的下标，表示为
\(\forall x \in N\),
\((2x+1) \operatorname{xor} 1=2x\),
且 $ 2x \operatorname{xor} 1=2x+1$
【网络流】EK Dinic 算法 相关文章
- 网络流入门5（最大流算法Dinic）
网络流入门5（最大流算法Dinic） 之前一直在写分析，还没有认真介绍一下网络流，这篇是从网络流的定义，求最大流所常用的Dinic算法入手开始的。 参考：http://blog.csdn.net/lzoi_hmh/article/details/74940366 什么是网络流？ 网络流...
- 网络流二十四题 (十五）、P1251 餐巾计划问题 dinic+spf
网络流二十四题 (十五）、P1251 餐巾计划问题 dinic+spfa 跑费用流 飞快 突然发现费用流可以用dinic写，虽然快不了太多，但能快一点是一点。比如这题是用时最短的。 这题本身很简单： 左部图点表示每天剩的衣服，右部...
- 最小费用最大流EK模板
#includebits/stdc++.husing namespace std;const int maxn = 4e5;const int maxm = 4e5;namespace graph { int first[maxn], nex[maxn], e[maxn], w[maxn], cost[maxn], top = 1; void Add(int x, int y, int W, int C) { nex[++top] = first[x]; first[x]
- 最小费用最大流Dinic
每条边单位流量会花费价值，在跑出最大流的情况下要求费用最小 #include queue#include cstdio#include cstring#include algorithmusing namespace std;const int N = 5e3 + 5;int read(int x = 0, int f = 1, char c = getchar()) { for (; c '0' || c '9';
- 最大流dinic模板
https://www.luogu.com.cn/problem/P3376 #includebits/stdc++.husing namespace std;#define int long longconst int maxn = 4e5;const int maxm = 4e5;int n, m, s, t;int first[maxm], nex[maxm], e[maxm], w[maxm], tot = 1;int dep[maxn], cur[maxm];in
- POJ3281 Dining最大流（Dinic+建图?）
POJ3281 Dining最大流（Dinic+建图?） 点这里 题意： 有n头牛、f种食物和d种饮料。一种食物或一种饮料只能喂给一头牛，一头牛也只能吃一种食物和一种饮料。问最多能投喂几头牛。 题解： 看上去很想二分图的匹配问题，但是...
- 图论算法----网络流----最大流sap算法
图论算法----网络流----最大流sap算法 一、相关概念 1、流网络 流网络G=(V, E)是一个有向图，其中每条边(u,v)均有一非负容量c(u, v)≥0。 流网络中有两个特殊的顶点: 源点s和汇点t。 假定每个顶点都处于从源点到汇点的某条路径上，...
- 最大流基础（网络流基础概念+三个算法）
最大流基础（网络流基础概念+三个算法） 下面是由一道题引发的一系列故事。。。 题目链接 http://poj.org/problem?id=1273 Drainage Ditches Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 68920 Accepted: 26683 Description Every time it
- 网络流最大流增广路算法
网络流最大流增广路算法 最大流问题 最大流问题是给定源点 s 和汇点 t ，在允许从其他点中转的情况下，询问最多有多少个物品能从源点 s 运送到汇点 t 。 增广路算法 首先提出残量这个概念，残量指的是对应边上容量与...
- 算法基础（一）：网络流最大流分配(附python源码)
算法基础（一）：网络流最大流分配(附python源码) 目录 概念介绍 流(Flow) 网络流(Network flow) 流网络(G,s,t,c)(G,s,t,c)(G,s,t,c) 顶点??的级??????????(??)： 最大流最小割定理： 最大流求解 Ford_Fullkerson方法 最大容量增广（MCA，Maximum Capacity A...
- 【学习笔记】网络流算法简单入门
【学习笔记】网络流算法简单入门 【学习笔记】网络流算法简单入门 网络流是一种神奇的问题，在不同的题中你会发现各种各样的神仙操作。 而且从理论上讲，网络流可以处理所有二分图问题。 二分图和网络流的难度都在于...
- Dinic算法模板
没什么好说的，建议直接背过。 “Dinic的复杂度就是个笑话，跟放P一样” 看似 \(O(n^2m)\) 实则艹过 \(n=10^5,m=10^6\) #include bits/stdc++.husing namespace std;typedef long long ll;const int N=1e4+10,M=2e5+10,INF=1e8;int n,m,s,t;int head[N],ver[
- RTSP/Onvif协议GB/T28181协议网络摄像头流转化过程中添加算法分
RTSP/Onvif协议、GB/T28181协议网络摄像头流转化过程中添加算法分析的方法 最近，经常遇到用户在使用我们产品的过程中，不仅限于单纯的使用音视频流转化、分发这些基础能力层功能，更多的开始运用智能分析技术。我们知道，...
- 令牌桶限流算法和漏桶限流算法区别
令牌桶限流算法和漏桶限流算法区别 1.漏桶限流算法的原理 以固定速率从桶中流出水滴，以任意速率往桶中放入水滴，桶容量大小是不会发生改变的。 流入：以 任意速率 往桶中放入水滴。 流出：以 固定速率 从桶中流出水滴...
- Kubernetes--k8s---进阶--AWS托管式容器服务EKS--EKS全面介绍和
Kubernetes--k8s---进阶--AWS托管式容器服务EKS--EKS全面介绍和安装使用 EKS简介 Kubernetes是Google开源的一个容器编排引擎，它支持自动化部署、大规模可伸缩、应用容器化管理。在Kubernetes中，我们可以创建多个容器，每个容器里面运行...
- 网络流之最大流最小割
简介 没什么好介绍的，作为一个只靠背代码会的dinic，本没什么发言权（毕竟建图才是精华（脸红）） 最小割比最大流有趣(恶心)多了 通常网络流的题目数据范围别出心裁，在[50,10000]间，除了DFS想不出别的方法 其中，构造...
- 负载平衡问题（费用流，网络流24题）
题意 有 \(n\) 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量\(a_i\)不等。 如何用最少搬运量可以使 \(n\) 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。 数据保证一定有解。 思路 这道题与运输问...
- 运输问题（费用流，网络流24题）
题意 有 \(m\) 个仓库和 \(n\) 个零售商店。第 \(i\) 个仓库有 \(a_i\) 个单位的货物；第 \(j\) 个零售商店需要 \(b_j\) 个单位的货物。货物供需平衡，即\(\sum_{i = 1}^m a_i = \sum_{j=1}^nb_j\)。 从第 \(i\) 个仓库运送每单位货物到第 \(j\) 个零售...
- 星际转移问题（最大流，分层图，并查集，网络流24题）
题意 思路 这道题有两个量，一个是人数（作为限制条件），另一个是天数（作为优化目标）。遇到这种问题，一般考虑分层图，将优化目标作为层。 这道题将\(n + 2\)个空间站（包括地球和月球）作为节点，将天数作为层，即每...
- 网络流学习笔记（1）：最大流及其反向边详解
网络流学习笔记（1）：最大流及其反向边详解 何为最大流？ 把计算机当做顶点，连接计算机的通信电缆当做边，就可以把该网络就可以把这个网络当作一个有向图来考虑了。图中的每条边 e ∈ E e\in E e ∈ E 都有对应的最大可能...