Max flow最大流(Introduction to Algorithms, 算法导论，CLRS)学习笔记_the value of the flow-程序员宅基地

技术标签： 算法  算法导论(Introduction to Algorithms CLR  数据结构  算法导论  

Max Flow

1. Foundations

  • What we do in Max flow: Given a flow network G with source s s s and sink t t t, to find a flow of maximum value

  • What is a valid flow: must satisfy both: 1. flow constraint; 2. flow conservation

2. Define a max-flow problem

  • G = ( V , E ) ; ( u , v ) ∈ E ; c ( u , v ) ≥ 0 G=(V,E);(u,v)\in E;c(u,v)\ge0 G=(V,E);(u,v)∈E;c(u,v)≥0
  • Capacity constraint: 0 ≤ f ( u , v ) ≤ c ( u , v ) 0\le f(u,v) \le c(u,v) 0≤f(u,v)≤c(u,v)
  • Flow conservation: for all v ∈ V v\in V v∈V{(s,t)}: ∑ v ∈ V f ( v , u ) = ∑ v ∈ V f ( u , v ) \sum_{v\in V}f(v,u)=\sum_{v\in V}f(u,v) ∑v∈V​f(v,u)=∑v∈V​f(u,v) the amount of flow going into u u u must be equal to flow going out of u u u
  • The value of a flow(graph): ∣ f ∣ = ∑ v ∈ V f ( s , v ) − ∑ v ∈ V f ( v , s ) |f|=\sum_{v\in V}f(s,v)-\sum_{v\in V}f(v,s) ∣f∣=∑v∈V​f(s,v)−∑v∈V​f(v,s) the value of a graph equals to the absolute value of source s s s
  • How to handle networks with multiple sources ad sinks: supersource and supersink
  • Modeling problems with antiparallel: add a new vertex
  • Skew Symmetry: F < x , y > = − F < y , x > F<x,y>=-F<y,x> F<x,y>=−F<y,x>

Residual network

  • Residual network: the residual network G f G_f Gf​ consists of edges with capacities that represent how we can change the flow on edges of G G G

  • Residual capacity: c

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_38356492/article/details/108982744

智能推荐

CAN总线之ISO15765协议（内含协议解析伪代码）-程序员宅基地

文章浏览阅读4.7w次，点赞45次，收藏315次。ISO 15765协议是一种CAN总线上的诊断协议。其中ISO 15765-1包括物理层和数据链路层，ISO 15765-2对网络层进行说明，ISO 15765-3则是规定到应用层的具体服务。 下面重点看下网络层，根据ISO 15765-2中的定义，网络层的功能是接收到应用层发送过来的消息流后，根据定义中的分包、位填充和时间控制等步骤，对消息流进行控制传输。流控制输有单帧传输、多帧传..._iso15765

Latex自动生成插图和表格目录_\listoffigures-程序员宅基地

文章浏览阅读1.2w次，点赞5次，收藏6次。生成插图目录的命令\listoffigures可以自定义目录名\renewcommand\listfigurename{插\ 图\ 目\ 录}生成表格目录的命令\listoftables可以自定义目录名\renewcommand\listtablename{表\ 格\ 目\ 录}..._\listoffigures

springcloud（9.2）Alibaba-Sentinel 控制台_springcloud sentinel控制台可以单独部署吗-程序员宅基地

文章浏览阅读1k次。Dashboard控制台sentinel-dashboard是一个单独的应用，通过spring-boot进行启动，主要提供一个轻量级的控制台，它提供机器发现、单机资源实时监控、集群资源汇总，以及规则管理的功能。启动控制台下载代码并编译控制台下载控制台工程 使用以下命令将代码打包成一个 fat jar:mvn clean package启动使用如下命令启动编译后的控制台..._springcloud sentinel控制台可以单独部署吗

栈的实现及基本操作pta栈的操作_给定一个初始为空的栈和一系列压栈、弹栈操作,请编写程序输出每次弹栈的元素。栈-程序员宅基地

文章浏览阅读3.4k次。**栈的实现及基本操作**给定一个初始为空的栈和一系列压栈、弹栈操作，请编写程序输出每次弹栈的元素。栈的元素值均为整数。输入格式:输入第1行为1个正整数n，表示操作个数；接下来n行，每行表示一个操作，格式为1 d或0。1 d表示将整数d压栈，0表示弹栈。n不超过20000。输出格式:按顺序输出每次弹栈的元素，每个元素一行。若某弹栈操作不合法（如在栈空时弹栈），则对该操作输出invalid。代码实现如下：#include#define N 20000typedef int Status;_给定一个初始为空的栈和一系列压栈、弹栈操作,请编写程序输出每次弹栈的元素。栈

《不懂项目管理，还敢拼职场》读后感_不懂项目管理,还敢拼职场读后感-程序员宅基地

文章浏览阅读393次。（1）把不起眼的活干得有声有色（2）要有自己的观点，否则只是个好试验员（3）开会是为了达成共识，指定行动方案（4）成功的创业者并不是勇于面对风险的人，而是善于管理和规避风险的人（5）能力再强，也要尊重上司（6）个人的优势需要化为团队的优势才能达到目标（7）项目的成功是由所有可交付成果组成的（8）合理的时间估算方法有：三点估算法：（最悲观时间+4最可能时间+最乐观时间）/6最乐观时..._不懂项目管理,还敢拼职场读后感

WAPI_wapi开发-程序员宅基地

文章浏览阅读683次。http://baike.baidu.com/view/63613.html?wtp=ttjust like TD-SCDMA_wapi开发

随便推点

【UR#13】【UOJ188】Sanrd（min_25筛）-程序员宅基地

文章浏览阅读123次。传送门题解：题目的实际含义是要求所有合数的次大质因子（不去重）之和。考虑min_25的做法，设S(n,i)S(n,i)S(n,i)表示所有[1,n][1,n][1,n]的数，次大质因子大于等于pip_ipi​的次大质因子之和。考虑在剩下两个数的时候计算，显然就是看[pi,npit][p_i,\frac{n}{p_i^t}][pi​,pit​n​]里面有多少个质数，用min_25预处理一下...

【愚公系列】2023年10月 WPF控件专题 MediaElement控件详解-程序员宅基地

文章浏览阅读5w次，点赞3次，收藏4次。WPF控件是Windows Presentation Foundation（WPF）中的基本用户界面元素。它们是可视化对象，可以用来创建各种用户界面。WPF控件可以分为两类：原生控件和自定义控件。原生控件是由Microsoft提供的内置控件，如Button、TextBox、Label、ComboBox等。这些控件都是WPF中常见的标准用户界面元素。自定义控件则允许开发人员使用XAML和C#等编程语言来创建个性化的用户界面元素。自定义控件可以根据需求提供更多的功能和自定义化选项，以及更好的用户体验。_mediaelement

elementui展示多张图片_vue+element ui 上传多张图片或视频-程序员宅基地

文章浏览阅读55次。:limit="5"action=""accept=".jpg,.jpeg,.JPG,.JPEG,.png,.PNG"list-type="picture-card":on-preview="handlePictureCardPreview":on-remove="handleRemove2":http-request="handleUploadImage":before-upload="befo...

基于FPGA的高通滤波算法实现_高通滤波器fpga图像-程序员宅基地

文章浏览阅读3.4k次，点赞2次，收藏15次。一.算法原理计算公式：H（2,2）= f(2,2) - 1/9*滑框均值 + 100假设一幅图大小为302 * 302 * 8 bit 那么 在3*3的模板 滤波次数 就为 （302-3+1）*（302-3+1）= 300*300二.在FPGA中的原理1.原理介绍 图像输入以CameraLink协议为例，向FPGA输入300*300的图像，由于需要将图像的首行首列..._高通滤波器fpga图像

你真不敢说精通微服务架构深度解析：微服务采用前提康威定律吗？-程序员宅基地

文章浏览阅读610次，点赞14次，收藏26次。这份文档从构建一个键值数据库的关键架构入手，不仅带你建立起全局观，还帮你迅速抓住核心主线。除此之外，还会具体讲解数据结构、线程模型、网络框架、持久化、主从同步和切片集群等，帮你搞懂底层原理。相信这对于所有层次的Redis使用者都是一份非常完美的教程了。你的支持，我的动力；祝各位前程似锦，offer不断！！！《互联网大厂面试真题解析、进阶开发核心学习笔记、全套讲解视频、实战项目源码讲义》点击传送门即可获取！全套讲解视频、实战项目源码讲义》点击传送门即可获取！**

电子元器件行业发展势头强劲，钧崴电子IPO上市抢占市场份额-程序员宅基地

文章浏览阅读757次，点赞3次，收藏6次。近年来中国电子工业持续高速增长，带动电子元器件产业强劲发展。目前，钧崴电子已能够提供上千种规格的产品，产品广泛应用于智能手机、笔记本电脑、平板电脑、移动电源、智能手表、蓝牙耳机、空调、冰箱、洗衣机、电视、扫地机器人、智能安防、电动工具等众多领域。目前，钧崴电子的产品已经成功应用在包括三星、小米、联想、新能德、格力、美的、大金、奥海科技、台达、欣旺达、海康威视、大华、视源股份、传音、戴尔、大疆、TTI等数十家国内外知名的智能手机品牌商、可穿戴设备厂商、电源厂商、家电集团、电动工具制造商的产品中。_钧崴电子ipo

推荐文章

热门文章

相关标签