最新要闻
- 特斯拉降价后:门店半小时售10台 老车主直呼被损失4万
- 焦点速读:特斯拉降价引海外热议:这是《孙子兵法》!欲消灭传统车企
- 你拿多少?报告称2022年终奖人均2.19万元 一线城市近3万元
- 环球今日讯!果香浓郁!徐福记DODO综合果味棒棒糖 60支19.9元
- 【世界速看料】保护隐私!微信键盘iOS 1.0.2版更新:体积膨胀到237MB
- 全球观天下!联想GeekPro 2023主机首销6199元起:13代i5+RTX 3060
- 【天天快播报】春节前最后一次成品油调价来了!或迎2023年首次降价
- 关注:畅想未来:2023年手机还能怎样进化?
- 对话郑刚:与罗永浩分歧关键不是商业利益
- 最野性的福特SUV!探险者Timberline亮相:超帅黑橙配色
- 33.58万起!比亚迪腾势D9成交付最快破万高端MPV
- 天天通讯!《魔兽世界》国服关闭倒计时!网易向玩家发短信安利《逆水寒》
- 从超前点映到480P投屏 视频平台赚钱只能靠“割韭菜”?
- 环球快消息!程序猿创造的AI虚拟漂亮老婆 被真女友强制“安乐死”了
- 天天热议:液金+水冷压住RTX 40系显卡:机械革命晒新旷世笔记本散热系统
- 特斯拉海外大降价!老外车主气炸请求维权:免费送FSD
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
全球热点!算法学习笔记(8.1): 网络最大流算法 EK, Dinic, ISAP
网络最大流
目录前置知识以及更多芝士参考下述链接网络流合集链接:网络流
- 网络最大流
- EK 增广路算法
- Dinic
- ISAP
- 作者有话说
最大流,值得是在不超过管道(边)容量的情况下从源点到汇点最多能到达的流量
抽象一点:使 \(\sum_{(S, v) \in E} f(S, v)\) 最大的流函数被称为网络的最大流,此时的流量被称为网络的最大流量
(相关资料图)
有了最大流量,就可以通过奇奇怪怪的建模解决很多令人摸不着头脑的题
例如二分图:
对于一张二分图,经过建模之后我们可以这样画
其中左部点集 \(A = \{1, 2, 3, 4\}\),右部点集 \(B = \{5, 6, 7, 8\}\), 其中源点为 \(0\),汇点为 \(9\)
建模过程:
新增一个源点 \(S\) 和一个汇点 \(T\), 从 \(S\) 到每一个左部点连有向边,从每一个右部点到 \(T\) 连有向边,把原二分图的每条边看作从左部点到右部点的有向边,形成了一张 \(n + 2\) 个点 \(n + m\) 条边的网络。其中每一条边的容量都为 \(1\)。
不难发现,二分图的最大匹配数就等于网络的最大流量。求出最大流后,所有有有”流“经过的点,边就是匹配点,匹配边。
进一步的:如果要求二分图多重匹配,依据题目信息改变连接汇点和源点的边的容量即可
计算最大流的算法很多,这里主要讲解 \(EK (Edmonds-Karp)\) ,\(Dinic\) 和 \(ISAP\) 算法。
EK 增广路算法
这里的增广路与二分图里面的增广路有不一样了 Q^Q
增广路:若一条源点 \(S\) 到 \(T\) 的路径上各边的剩余容量都严格大于\(0\),则称这条路径为增广路。显然,可以让一个流沿着增广路流过,使得网络的流量增大。
而\(EK\)的思路就是不断进行广度优先搜索寻找增广路,直到不存在增广路为止。
而在搜索的时候,我们只考虑图中所有 \(f(x, y) < c(x,y)\) 的边(或者说是有剩余容量的边)。在寻找路径的同时,还要记录其前驱结点以及路径上的最小容量\(minf\), 在找到一条增广路后,则网络的流量可以增加 \(minf\)。
但是,考虑到斜对称的性质,由于我们需要把增广路上的所有边的剩余容量 \(e(u, v)\) 减去\(minf\),所以要在对其反边容量 \(e(v, u)\) 加上 \(minf\)。
初始化的时候,如果是有向边 \((u, v)\),则 \(e(u, v) = c(u, v), e(v, u) = 0\),如果是无向边,则 \(e(u, v) = e(v, u) = c(u, v)\)。
?: 为什么会出现无向边,网络流不是有向图吗?
考虑双向道路
马路,既可以顺流,又可以逆着。例如:[ICPC-Beijing 2006] 狼抓兔子 - 洛谷
这道题需要用到最小割,顺便说一下,最小割 = 最大流
?: 为什么使用BFS,而不是DFS?
因为DFS可能会绕圈圈……在讲述DInic的时候我会再提及
复杂度:复杂度上界为 \(O(nm^2)\),然而实际上远远达不到这个上界,效率还行,可以处理 \(10^3 \sim 10^4\) 规模的网络
--《算法竞赛进阶指南》
我不会证明,下面的两个算法也不会 Q^Q
这里给出一种参考代码
【模板】网络最大流 - 洛谷
提交记录:记录详情
#include #include #include #include using std::deque;const int N = 2e3 + 7, M = 5e5 + 7, INF = 0x7F7F7F7F;int n, m, s, t;int to[M], nex[M], wi[M] = {INF};int head[N], tot = 1;void add(int u, int v, int w) { to[++tot] = v, nex[tot] = head[u], wi[tot] = w, head[u] = tot;}void read() { scanf("%d %d %d %d", &n, &m, &s, &t); int u, v, w; for (int i = 0; i < m; ++i) { scanf("%d %d %d", &u, &v, &w); add(u, v, w); add(v, u, 0); }}#define min(x, y) ((x)<(y)?(x):(y))#define pop() que.pop_front()#define top() que.front()#define push(x) que.push_back(x);#define empty() que.empty()static int inq[N], it = 0;static int px[N], pe[N];inline int bfs() { deque que; push(s); inq[s] = ++it; int x, y; while (!empty()) { x = top(); pop(); for (int i = head[x]; i; i = nex[i]) { if ((inq[(y = to[i])] ^ it) && wi[i]) { px[y] = x, pe[y] = i; if (y == t) return 1; inq[y] = it; push(y); } } } return 0; // 到不到了,没有增广路了}void work(long long & res) { while (bfs()) { int val = INF; for (int x = t; x ^ s; x = px[x]) { val = min(val, wi[pe[x]]); } for (int x = t; x ^ s; x = px[x]) { wi[pe[x]] -= val; // 处理反边的时候利用了成对变换的方法! wi[pe[x] ^ 1] += val; } res += val; }}int main() { read(); long long res = 0; work(res); printf("%lld\n", res); return 0;}
Dinic
考虑到 \(EK\) 算法每一次在残量网络上只找出来的一条增广路,太慢了,所以有了更优化的东西 Dinic?歌姬吧
先引入一点点概念:
深度:在搜索树上的深度(BFS搜索时的层数)
残量网络:网络中所有节点以及剩余容量大于 \(0\) 的边构成的子图
分层图:依据深度分层的一段段图……或者说在残量网络上,所有满足 \(dep[u] + 1 = dep[v]\) 的边 \((u, v)\) 构成的子图。
分层图显然是一张有向无环图
Dinic 算法不断重复下述过程,直到在残量网络中,\(S\) 不能到达 \(T\)
利用BFS求出分层图
在分层图上DFS寻找增广路,在回溯的时候实时更新剩余容量。另外,每个点可以同时流出到多个结点,每个点也可以接收多个点的流。
?: 这里为什么可以使用DFS
由于我们分了层,意味着DFS只会向更深的地方搜索,而不会在同一层乱跳,甚至搜索到前面。这也是为什么EK用BFS更优秀
复杂度:一般来说,时间复杂度为 \(O(n^2m)\),可以说是不仅简单,而且容易实现的高翔算法之一,一般能够处理 \(10^4 \sim 10^5\) 规模的网络。特别的,用此算法求二分图的最大匹配时只需要 \(O(m\sqrt{n})\), 实际上表现会更好。
题目不变
没有当前弧优化:提交详情
有当前弧优化:记录详情
// 重复内容已省略int dis[N], vis[N], vt = 0;int now[N]; // 用于当前弧优化// return true if exists non-0 road to tbool bfs() { memset(dis, 0, sizeof(dis)); dis[s] = 1; deque que; que.push_back(s); while (que.size()) { int x = que.front(); que.pop_front(); now[x] = head[x]; // 更新当前弧 for (int y, i = head[x]; i; i = nex[i]) { if (!dis[y = to[i]] && wi[i]) { dis[y] = dis[x] + 1; que.push_back(y); if (y == t) return true; } } } return false;}#define min(x, y) ((x) < (y) ? (x) : (y))long long dinic(int x, long long maxflow) { if (x == t) return maxflow; long long rest = maxflow, k; for (int y, i = now[x]; i && rest; i = nex[i]) { now[x] = i; // 更新当前弧 if (dis[y = to[i]] == dis[x] + 1 && wi[i]) { k = dinic(y, min(rest, wi[i])); if (!k) dis[y] = 0; wi[i] -= k, wi[i ^ 1] += k; rest -= k; } } return maxflow - rest;}int main() { read(); long long maxflow = 0, flow; while (bfs()) { while (flow = dinic(s, INF)) maxflow += flow; } printf("%lld\n", maxflow);}
?: 当前弧优化是个啥玩意
注意到如果我们每一次遍历后,对于当前边 \((u, v)\),不可能再有流量流过这条边,所以我们可以暂时的删除这条边……注意,只是暂时,每一分层的时候是需要考虑这条边的,因为这条边的剩余流量不一定为 0
ISAP
某位大佬的博客上说这是究极最大流算法之一。还有一个HLPP(最高标记预留推进),思路完全与这几个方法不同,不依赖于增广路,我会把它放在另外的文章中单独讲。
我可不会告诉你们是我不会优化,太笨了,看不懂大佬的优化题目链接:【模板】最大流 加强版 / 预流推进 - 洛谷
这是我的:记录详情 4.77s
这是大佬的:记录详情 185ms
由于Dinic需要多次BFS……所以有些不满足的数学家决定优化常数……于是有了ISAP,只需要一次BFS的东西……
可恶,竟然没有找到不用gap优化的写法 T^T
ISAP算法从某种程度上是SAP算法和Dinic的融合
SAP算法就是所谓的EK算法……ISAP也就是Improved SAP……但是主体怎么跟DInic几乎一模一样!
算法流程如下:
从 \(T\) 开始进行BFS,直到 \(S\) ,标记深度,同时记录当前深度有多少个
利用DFS不断寻找增广路,思路与Dinic类似
每次回溯结束后,将所在节点深度加一(远离 \(T\) 一点),同时更新深度记录。如果出现了断层(有一个深度没有点了)那么结束寻找。
怎么跟Dinic一摸一样啊,关键是也可以用当前弧优化,只是我用写的是vetor存图……用不了
参考代码……
提交题目还是【模板】网络最大流 - 洛谷
记录详情
!! 竟然在最优解第二页 O-O
// 写这个的时候,借鉴了写HLPP最优解的大佬写快读的方法……templateinline void read(T &x) { char c, f(0); x = 0; do if ((c = getchar()) == "-") f = true; while (isspace(c)); do x = (x<<3) + (x<<1) + (c ^ 48), c = getchar(); while (isdigit(c)); if (f) x = -x;}template inline void read(T &t, Args&... args) { read(t), read(args...); }typedef long long Data;using namespace std;const int N = 207, M = 5007;struct Edge { int to; size_t rev; // 反边的位置,用int也没问题 Data flow; Edge(int to, size_t rev, Data f) : to(to), rev(rev), flow(f) {}};class ISAP {public: int n, m, s, t; vector dep; int q[N * 2], gap[N * 2]; // vector< vector > v; vector v[N * 2]; ISAP(int n, int m, int s, int t) : n(n), m(m), s(s), t(t) { input(); } inline void input() { // v.resize(n + 1); for (int x, y, f, i(0); i ^ m; ++i) { read(x, y, f); v[x].push_back(Edge(y, v[y].size(), f)); v[y].push_back(Edge(x, v[x].size() - 1, 0)); } } inline void init() { dep.assign(n + 1, -1); dep[t] = 0, gap[0] = 1; // 如果要用手写队列,要开大一点……避免玄学RE,虽然理论上N就够了 register int qt(0), qf(0); q[qt++] = t; int x, y; while (qf ^ qt) { x = q[qf++]; for (auto &e : v[x]) { if (dep[(y = e.to)] == -1) // if dep[y] != -1 ++gap[(dep[y] = dep[x] + 1)], q[qt++] = y; } } // bfs end } inline Data sap(int x, Data flow) { if (x == t) return flow; Data rest = flow; int y, f; for (auto &e : v[x]) { if (dep[(y = e.to)] + 1 == dep[x] && e.flow) { f = sap(y, min(e.flow, rest)); if (f) { e.flow -= f, v[e.to][e.rev].flow += f; rest -= f; } if (!rest) return flow; // flow all used } } // change dep if (--gap[dep[x]] == 0) dep[s] = n + 1; // can not reach to t ++gap[++dep[x]]; // ++depth return flow - rest; } inline Data calc() { Data maxflow(0); static const Data INF(numeric_limits::max()); // dep[s]最大为n,为一条链的时候 while (dep[s] <= n) { // 如果要当前弧优化,在这里需要重置当前弧的now! maxflow += sap(s, INF); } return maxflow; }};int main() { int n, m, s, t; read(n, m, s, t); static ISAP isap(n, m, s, t); isap.init(); printf("%lld\n", isap.calc()); return 0;}
作者有话说
一般来说,如果图非常稠密(边数远远大于点数),当前弧优化的力度就非常大了
如:Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流 - 洛谷
写了当前弧优化的Dinic能轻松过……没写全TLE
虽然没写当前弧优化的ISAP能更快的过前三个点,但最后一个点过不了……QwQ
没试过写当前弧优化的ISAP
但是如果边数不多,当前弧优化可能就成了负优化了……所以需要根据题目数据合理使用
-
学习笔记——Spring简介;Spring搭建步骤;Spring的特性;Spring中getBean三种方式;Spring中的标签
2023-01-13一、Spring1、Spring简介(1)Spring是一个为简化企业级开发而生的开源框架。(2)Spring是一...
来源: 全球热点!算法学习笔记(8.1): 网络最大流算法 EK, Dinic, ISAP
学习笔记——Spring简介;Spring搭建步骤;Spring的特性;Spring中getBean三种方式;Spring中的标签
实时:AcWing257 关押罪犯
当前关注:使用vscode调试PHP底层C源码
特斯拉降价后:门店半小时售10台 老车主直呼被损失4万
焦点速读:特斯拉降价引海外热议:这是《孙子兵法》!欲消灭传统车企
你拿多少?报告称2022年终奖人均2.19万元 一线城市近3万元
环球今日讯!果香浓郁!徐福记DODO综合果味棒棒糖 60支19.9元
【世界速看料】保护隐私!微信键盘iOS 1.0.2版更新:体积膨胀到237MB
全球观天下!联想GeekPro 2023主机首销6199元起:13代i5+RTX 3060
【天天快播报】春节前最后一次成品油调价来了!或迎2023年首次降价
关注:畅想未来:2023年手机还能怎样进化?
对话郑刚:与罗永浩分歧关键不是商业利益
最野性的福特SUV!探险者Timberline亮相:超帅黑橙配色
33.58万起!比亚迪腾势D9成交付最快破万高端MPV
天天通讯!《魔兽世界》国服关闭倒计时!网易向玩家发短信安利《逆水寒》
从超前点映到480P投屏 视频平台赚钱只能靠“割韭菜”?
环球快消息!程序猿创造的AI虚拟漂亮老婆 被真女友强制“安乐死”了
天天热议:液金+水冷压住RTX 40系显卡:机械革命晒新旷世笔记本散热系统
特斯拉海外大降价!老外车主气炸请求维权:免费送FSD
环球关注:4K缩水到480p 爱奇艺称“有权变更内容” 律师回应称肯定违约了
环球讯息:《流浪地球2》发行通知公开:片长173分钟对标《阿凡达2》
时讯:网友铁了心要等一加11 Pro 李杰:没有11 Pro、11 Ultra
遭黑客广泛利用:微软无奈计划淘汰诊断工具MSDT
你涨工资没?全国招聘平均月薪增幅最高城市 最低1.2万、还在加薪
世界微速讯:曾两个月涨粉上千万!张同学回应热度消退:可以坦然面对
视点!小米6钉子户换上Redmi K50至尊版:速度就是快
马斯克突然调整Twitter API:第三方客户端全灭
不再是小仪表盘 新款比亚迪秦PLUS DM-i曝光:续航猛增至1310km
热点聚焦:燃油版“宏光MINIEV”!三菱Delica Mini首发:配0.66L发动机
【环球快播报】“蓝兔”邮票黄永玉有多潇洒?北京第一辆私家车拥有者 93岁开法拉利飙车
每日信息:三星将长焦发挥到极致!曝Galaxy S24 Ultra支持150倍变焦
快资讯:iPhone 14兔年限量保护套售价398元贵吗?部分型号卖断货
TP-LINK发布新款AX3000双频千兆Wi-Fi 6光口AP:支持DC、PoE双供电
世界微速讯:长白山人参旗舰店:全须生晒参4盒99元狂促(300元大额券)
播报:联想拯救者刃7000K 2023今日开售:i5-13400F+RTX3060 首发7199元
焦点热议:豆瓣9.5高分国漫!《中国奇谭》第二季已在筹备:要打造IP宇宙
最新快讯!二十六位朗读主播!讯飞有声书图赏
当前热讯:“1888万彩礼”事件作者承认编故事 知乎:永久封禁账号
热资讯!奇葩公司发大鹅当年货 员工开心又无奈:放公司很吵
天天微速讯:故意排放能怎样?日本决定核废水2023春夏排入海 多国网友愤怒
2022年动力电池装车量排名:“宁迪”双王吃下超7成市场
每日关注!73岁保安徒手接住4楼坠落女子获奖 网友:见义勇为、值得点赞
HarmonyOS智能座舱是怎样炼成的?华为官方揭秘软件开发标准
全球讯息:大手笔!蔚来官宣:春节高速路换电全免费、不限次数
今日最新!(六)elasticsearch 源码之选主流程分析
环球今日讯!java中关于继承,多态及方法调用的底层细节
如何构建基于 DDD 领域驱动的微服务?
世界新资讯:火山引擎 DataTester:一次 A/B 测试,帮助产品分享率提升超 20%
珠江的源头在哪里?珠江的长度是多少千米?
当前热文:被称作“电费刺客” 商家:踢脚线取暖器耗电量可达空调3倍
蜀国的皇帝有哪些?蜀国的皇帝列表排名
当前视点!明晚8点开播!央视网络春晚第二波阵容官宣:王心凌、撒贝宁等加盟
魔兽国服关闭当天 老外喜迎新版本升级 网友:暴雪杀人诛心
豆瓣9.2分神作!《新·福音战士剧场版:终》终于官宣引进
天天时讯:2023年电脑城奸商依然猖狂:3千元笔记本卖5千 出库不能退
为黛西小姐开车故事背景是什么?为黛西小姐开车故事梗概是什么?
打电动是什么意思?打电动是什么游戏?
特百惠是哪国的牌子?特百惠卖什么产品?
电视机顶盒怎么连接电视机?电视机顶盒怎么破解?
怎么给冰箱加氟?冰箱加氟一般需要多少钱?
excel怎么转化为在线表格?excel怎么转化为PDF?
lol怎么亮徽章?lol徽章有什么用?
斗鱼鱼丸多少钱一个?斗鱼鱼丸怎么兑换人民币?
用SGDK开发世嘉MD游戏:入门篇
快资讯:FAA飞航系统已有30年历史 老迈程度堪比N64
环球百事通!90后女孩神还原蔡明春晚40年造型火了 本尊回应5个字
焦点观察:果粉愿望要实现!iPhone 16 Pro直接256GB存储起步
环球快消息!12月轿车销量排名出炉:传统“豪强”反攻、比亚迪也挡不住?
世界观点:超大范围降雪来袭:全国多地上百条高速局部路段公路封闭
最新:误将磁盘格式化的应急响应
头条:【Python爬虫项目实战】Python爬虫豆瓣Top250电影短评数据保存本地
2023最新nacos的windows 10安装(保姆级)
滚动:我国让科幻片成了现实!全球首艘智能型无人系统科考母船交付使用
世界热点评!6英寸墨水屏带来全新听书体验!讯飞有声书评测:内置26种朗读主播 方言英语都能读
全球观速讯丨微软经典Media Player获新生:新版本面向全部Win10用户推出
焦点快看:读编程与类型系统笔记06_函数类型的高级应用
全球热消息:NVIDIA发布GeForce 527.37驱动 4倍性能提升的DLSS3游戏再加一
焦点播报:苹果A处理器不玩性能!iPhone 16曝光:屏幕更完美、2TB售价欲超2万
环球信息:美国家庭平均月薪出炉引热议:超出想象!就这还靠信用卡续命
你贡献过几部iPhone?全球最强打工人:苹果库克年薪近1亿美元 自愿降薪40%
每日速递:监管新规下车险保费最高可降23%?业内人士:有些还会变贵
天天即时看!打破多项纪录!我国汽车产销总量连续14年全球第一:新能源暴涨翻倍
《王者荣耀》兔年春节福利一览:武则天神器传说皮肤来了
我国第一型“金牌火箭” 长二丙火箭成功发射亚太6E卫星
全球动态:[概率论与数理统计]笔记:3.5 大数定律与中心极限定理
环球滚动:Spring Cloud Alibaba 2022.0.0.0 版本发布啦!
国产高端手机份额第一!卢伟冰:小米13系列好评99% 自然销量高
【天天快播报】史上第一颗6GHz CPU!i9-13900KS发布:性能涨3% 价格涨20%
理想汽车CEO曾试图接触威马沈晖?本人回应:纯属放屁!
世界新资讯:韩国第一个月球探测器发回第一张照片:地月黑白合影
每日资讯:【深度学习】常用PyTorch CUDA版本whl下载及在线安装命令
世界今日讯!「闲话随笔」势能分析法
全球短讯!MQ——如何选择消息队列
微头条丨女子乘火车遇麻将专列生意火爆 还能K歌引围观:网友直呼想买站票
全球观焦点:三级应急响应启动!寒潮预警升级 降温图又变紫了:局地降超20度
天天观天下!盖茨自曝他的主力机是三星Galaxy Z Fold4:李在镕送的
全球热文:《卧龙:苍天陨落》中配预告 声优大佬云集、虎牢关战吕布超燃
学习笔记——Mybatis中缓存机制
播报:区块链特辑——solidity语言基础(五)