博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
『算法』Dinic求最大流
阅读量:6102 次
发布时间:2019-06-20

本文共 1536 字,大约阅读时间需要 5 分钟。

作为一个【NOIP+,省选-】算法,这个算法真的很暴力。同样是最大流,跑得比EK不知快到哪里去了。首先是一个

广度优先搜索(){    按照可用路径上节点的访问顺序标号。    然后判断一下能否到汇点。    如果不能(汇点没有被标号),那么返回不行。    否则返回行。}然后,只要能找到到汇点的路,就进行一个深度优先搜索(当前到的那个节点了,现在的最大流){    维护一个当前用过的流量 = 0。    对于它的每条连接儿子节点的边:        如果这个儿子被编的号是它的号加一:            那么最大流就变成了min(儿子能流的流量,当前的流量)。            当然,当前的流量要继续深搜。              儿子的入边减去最大流。            儿子的出边加上最大流。            当前用过的流量加上最大流。            如果当前用过的流量等于最大流的话:                就返回当前用过的流量    如果当前用过的流量是0的话        就把当前节点的值设为-1(不走了)    否则        就返回当前用过的流量。} 算法主体() {     只要还能广度优先搜索:         答案就加上深度优先搜索(源点,正无穷)。 }输出答案就好啦!
bool bfs(){    std::queue
q; q.push(S); std::memset(pre, 0, sizeof pre); while (!q.empty()) { int x = q.front(); q.pop(); for (int t = head[x]; t; t = next[t]) if (!pre[lis[t]] && v[t]) { pre[lis[t]] = pre[x] + 1; q.push(lis[t]); } } if (!pre[T]) return false; return true;}int dfs(int pos, int flow){ if (pos == T) return flow; int w, t, used = 0; for (int t = head[pos]; t; t = next[t]) { if (v[t] && pre[lis[t]] == pre[pos] + 1) { w = Dinic(lis[t], std::min(flow - used, v[t])); used += w; v[t] -= w; v[t + 1] += w; if (used == flow) return flow; } } if (!used) pre[pos] = -1; return used;}void Dinic(){ while (bfs()) ans += dfs(S, INT_MAX);}

转载于:https://www.cnblogs.com/edwardtsui/p/6782857.html

你可能感兴趣的文章
ubuntu apt-get 安装 lnmp
查看>>
焊盘 往同一个方向增加 固定的长度方法 总结
查看>>
eclipse的maven、Scala环境搭建
查看>>
架构师之路(一)- 什么是软件架构
查看>>
jquery的冒泡和默认行为
查看>>
USACO 土地购买
查看>>
【原创】远景能源面试--一面
查看>>
B1010.一元多项式求导(25)
查看>>
10、程序员和编译器之间的关系
查看>>
前端学习之正则表达式
查看>>
配置 RAILS FOR JRUBY1.7.4
查看>>
AndroidStudio中导入SlidingMenu报错解决方案
查看>>
修改GRUB2背景图片
查看>>
Ajax异步
查看>>
好记性不如烂笔杆-android学习笔记<十六> switcher和gallery
查看>>
JAVA GC
查看>>
codeforce 599B Spongebob and Joke
查看>>
3springboot:springboot配置文件(外部配置加载顺序、自动配置原理,@Conditional)
查看>>
9、Dubbo-配置(4)
查看>>
前端第七天
查看>>