- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
现在已知如下问题,并告诉你这题可以用网络流来解决,你该怎么做,该怎么建出网络流的模型?
显然可以发现绝不可能走横向向左的边,但可能走竖向向上的边(如下图) 。
那么图其实就是这样的:问从 \(s\) 到 \(t\) 的最小花费 。
如果没有那 \(m\) 条限制,我们直接跑最短路就行了,加上这些限制,发现其实是个网络流模型,考虑如何建出网络流模型.
我们虚构出以下的模型以方便理解——很典的模型:对偶图!(具体什么是对偶图自行了解) 。
注:没方向的边是现在还不清楚该怎么建,稍后考虑.
每条红边(网络流上的边)的权值就是其交叉的黑边(实际的图)的权值 。
(好像个灯笼)现在实际上从 s 到 t 的最短花费其实就是 s 到 t 的红色连边构成的图的最小割了.
为什么?我们单独扣出来两个点证明一下:
如上图,先不考虑横着的红边的话,根据最小割知识,我们知道在路径 \((s,x) 和 (x,t)\) 中必须要割掉一条且只割掉一条,同样,在 \((s,y) 和 (y, t)\) 中必须要割掉一条且只割掉一条,(必须割一条是为了满足没有增广路可以从 s 到 t ); 。
为什么各只能割掉一条呢?
对照实际的图,发现一样,如果走 1->2 这条边,一定不会走 4->5 这条边,走 2->3 一定不会走 5->6; 。
如果走了 2->5,那么要么是走 1->2->5->6,要么是走 4->5->2->3.
所以其实可以发现最小割就是原图中的最短路.
解决了以上问题,那么现在我们只需再解决 \(m\) 个限制条件 和 灯笼图中没有方向的红边(最左边和最右边点的边) 两个问题即可.
还是扣出两个点,(只扣模型点了),如果题目限制同时走 s->x 和 y->t (x 和 y 并不一定相邻)时,需要再增加大小为 \(c\) 的花费。(现在暂时当作没有虚线边) 。
那么等同于我们需要考虑如何使得在既割 s->x 又割 y->t 的情况下,还需要再多割一条花费为 \(c\) 的边,我们再建一条从 y 到 x ,花费为 \(c\) 的边就解决了。(就是图中虚线边).
显然割掉 s->x 和 y->t 后,还有一条增广路 s->y->x->t,所以必须再割掉 y->x,(上文已经证明出来此时不会再割 x->t 和 s->y )。ok 了.
现在把最右边那部分边拿出来,显然可以连成这样:
可以发现,在 1、2 边之间(显然这两条边只能走一个)如果我们走的是 2,则没什么事;但如果走的是 1 这条边,那么就一定要走 3 这条边。考虑在网络流上怎么解决?
意思就是需要在 a、b 之间选择割 a 这条边的时候,必须要再割掉 e 这条边.
其实把 d 权值附为 0,c 附为 inf,然后 e 从右边那个点连向左边那个即可,这样保证割 d 不割 c,此时若割 a,则还需要割掉 e 以使增广路 c-e-b 不再增广.
如下图:
最后此篇关于手把手教你建【货币】一题的网络流模型的文章就讲到这里了,如果你想了解更多关于手把手教你建【货币】一题的网络流模型的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
与其他许多不同,Coq 接受一个可选的显式参数,该参数可用于指示固定点定义的递减结构。 从 Gallina 规范,1.3.4, Fixpoint ident params {struct ident0
就目前而言,这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持,但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the he
前言:我目前正在学习 ANN,因为我在大约 83 个类别中有大约 18500 张图像。它们将用于训练 ANN 以实时识别大致相等的图像。我按照书中的图像示例进行操作,但它对我不起作用。所以我要回到开头
在我的程序中,我处理有时为 NULL 的 C 风格字符串(类型为 char *)。我想教 cout 优雅地处理这些问题(即打印“(null)”而不是段错误)。 我的第一次尝试: ostream& op
我正在开发一个采用(定制的)微线程解决方案的大型程序。有时我需要调试崩溃。在这种时候,能够从一个微线程切换到另一个微线程是很有用的。 如果我正在进行实时调试,我可以将所有寄存器替换为来自微线程上下文的
我可以教 Notepad++ 在它看到多行注释时应用折叠,其中注释以井号开头,多行注释是连续行上的井号吗? # This is a comment # It continues on the next
我被要求为一个 child 辅导 Pascal。尽管在我设法获得教程之前从未见过 Pascal,但我现在知道的足以教他了。 我给你们写信是想看看是否有人能给我指出一些涉及简单算法的基本练习,比如:对这
按照目前的情况,这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持,但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the
我正在维护来自外国情报监视法庭的大量编辑文件的文件。 它们带有大段文本,如下所示: 当 OCR 尝试处理此问题时,您会收到如下文本: production of this data on a dail
今年夏天,我将教高中生使用 C++ 编程。我必须在一周内教给他们 Material 。通读了公司给我的教程,他们建议我一开始就在程序中使用“include stdafx.h”。 你觉得呢 includ
我需要在他的笔记本电脑上安装一个 c# ide(免费),我需要下载 sdk 还是 windows 7 带有 c# 编译器? (从头开始设置已经有一段时间了) 最佳答案 你可以试试Visual C# 2
背景 我刚刚在 AWS 上启动了一个新的 Redshift 实例,我可以毫无问题地通过 psql cli 客户端连接到它。 问题 我正在尝试让我的 Rails 3 应用程序连接到 Redshift 盒
我是一名优秀的程序员,十分优秀!