1回答
我正在阅读Robert Sedgewick的算法第二卷。这一部分来自网络流量算法。流分解定理:任何循环都可以表示为沿一组至多E方向的边的流。推论1:任何st-网络都有一个最大流，使得由非零值诱导的子图是无圈的。
推论2:任何st-网络都有一个最大流，它可以表示为从s到t的至多E条有向路径的流。
浏览 3提问于2012-05-14得票数 1
2回答
添加边缘后更新最大流
、、、、
考虑到我们有一个网络流，并且使用Edmond算法，我们已经有了网络上的最大流。现在，如果我们在网络中添加一个任意的边缘(具有一定的容量)，那么更新最大流量的最佳方法是什么？我正在考虑更新关于新的边缘的剩余网络，并再次寻找增强路径，直到我们找到新的最大流量，但我不确定它是否工作或它是否是最好的方式！
浏览 6提问于2014-12-13得票数 4
回答已采纳
1回答
我实现了最大流的最高标签推送重标算法的第一阶段，但没有找到任何关于如何实现第二阶段的资源，即将预流推送网络转换为有效的流网络。
浏览 10提问于2014-11-14得票数 1
回答已采纳
1回答
一个满足以下条件的高效图算法？
、、、、
给定一个有n个顶点的无向图，我们需要选择一些边，即边数=m{ m>=1 m<=floor(n/2)}，使得它们不共享任何公共顶点，并且所有选定边的权重和最大化。我们需要找出所有选定边数(1到n/2)的最大和。
浏览 1提问于2019-11-09得票数 0
1回答
二部图的双匹配
、、
我在学习算法测试时遇到了以下问题，但没有给出答案：
1)对最大流进行约简:将顶点的s、t和边从s增加到L，边从R增加到t，每个边的容量为2，并用无限容量定
浏览 0提问于2018-07-05得票数 1
回答已采纳
1回答
我正在寻找一种算法，以检查是否在给定的网络流中有一个信号最小切割。
我知道这是可能的，因为我们可以寻找所有的削减，并检查我们是否只有一个最小的削减，但我想找到更有效的算法运行多项式。我想用最大流算法来帮助我，但我没有成功。
浏览 0提问于2014-07-05得票数 0
回答已采纳
1回答
一段时间前，我读到了一个通用的最小切割算法，它将一个图作为输入，并删除一个min。使两个断开的组件保持不变的边数。有没有有效的算法来得到一个值(最小值的基数。对于图中的每一对顶点)？作为这个主题的新手，如果有人能提供论文或其他资源的链接，概述在合理的运行时复杂性运行的算法，我将不胜感激。
谢谢!
浏览 1提问于2012-02-21得票数 8
回答已采纳
1回答
网络流中的“增长边”
、、、
我们得到了一个网络流，以及一个网络中的最大流。如果以任意正数增加边的容量，则称为增长边，也会增加最大流。
在剩余网络中运行BFS，以确定是否存在改进的路径。为了找到它，我们必须把原来的网络和新的网络进行比
浏览 4提问于2018-08-17得票数 1
1回答
我被要求为以下问题开发一个算法：A流网络G，其边的最大容量为1G的最大流f_x_xa正整数K_。，如果K大于或等于max，删除所有穿过G的最小割集的边，如果K仍然大于零，删除随机边，并且新的最大流是零如果K小于，则删除与G最小割集相关的边的K，且新的最大流为delete 。我需要一
浏览 0提问于2020-06-21得票数 0
回答已采纳
在最大流问题中，当我应用ford-fulkerson算法寻找最大流时，如果图的所有链接都有权重1，则最大流将是我在ford fulkerson算法中找到的路径数，对吗？我是说，dfs路径的数目。
浏览 4提问于2014-04-17得票数 1
回答已采纳
1回答
找到最大匹配
、、
描述一个有效的算法，以确定是否存在最大匹配。
基本上，给定的解决方案是通过添加s,t顶点，将s连接到A中的每个顶点v，将B中的每个顶点v连接到t，从而从图中构建一个流网络。所有容量均为1。现在，我们给出了所有边M (以及从s和t连接到M边的所有边)的起始流。现在，我们只需要运行折叠-Falkerson(或Edmond)算法，并检查我们是否能够改进2013路径(即为某些路径添加更多的流)。更准确地说，我们最多需要运行BFS， 2013 times来决定。就像我们假设M是最大<
浏览 5提问于2016-09-13得票数 1
回答已采纳
1回答
生成随机流网络
、、
我试图为给定的图形创建一个流网络，以便它可以用来测试一个算法。为了提供清晰性，我希望每个顶点的流相等于流出的流量。所有的流量都来自源头，流向水槽。每个边都有一个最大的容量和一个方向。我希望通过这个网络生成一个流量，它等于最大流(由最小剪切找到)，它永远不会超过每个边缘的容量。
下面是一个图形化的例子，说明我得到了什么和我想要得到什么。当然，“期望的流图”并不是一个独特的例子。第一个数组给出" from“顶点，第二个数组t给出" to”顶点，第三个数组
浏览 1提问于2017-04-28得票数 1
1回答
网络流更新值
、、
我正在练习我的书中的算法问题，我偶然发现了这个问题：
给出了一个有向网络G，它有n个节点和m个边，一个源，一个接收器t和一个从s到t的最大流f，假设每个边的容量是一个正整数，那么描述一个O(m + n)时间算法，在以下两种情况下更新流f。它看起来就像穿过网络流边和调整流量一样简单，但我不认为它真的那么简单。维基百科只给出O(n^2 m)或O(n m^2)的算法。任何帮助或想法都将不胜感激。
浏览 1提问于2014-11-19得票数 1
回答已采纳
1回答
我有一个带有一些边和节点的流网络。在离开源节点的边上，我想放置一些最小流，以便在该边上至少有x个流(如果这不可能，我想知道)。我已经实现了Ford-Fulkerson算法来寻找最大流量，但我不确定如何调整我的算法来实现这一点。我想过减少离开源节点的边的容量，但这对我不起作用。
谁能在这个问题上给我指引正确的方向？
浏览 2提问于2013-01-06得票数 2
回答已采纳
这个问题是关于网络流在项目选择中的应用。项目选择问题是指选择哪一组项目以实现收益最大化的问题。每个项目都有收入(正或负)。项目也有其他项目的先决条件。一组项目A是可行的，如果A中每个项目的前提也在A中，则项目选择问题是选择一组收益最大的可行项目集。将一个项目选择问题转化为一个网络流问题，并用Fulkerson算法进行求解。考虑下列一组项目：A，6，DC，-8E、7、C、D
我在这里感到困惑，因为C和D有负收入，我不知道如何将这个问题转化
浏览 3提问于2021-01-21得票数 2
回答已采纳
1回答
用于分配作业的递归
、、、、
为了让他们从事这项工作，他们必须接受培训，这样系统才能知道每个员工接受过和没有接受过培训的内容。
foreach($employees as $emp){ assign them; }}
这在某种
浏览 0提问于2013-05-25得票数 1
回答已采纳
我有一个无向图，想要计算两个顶点之间可能的最长路径，其中每条边只能访问一次，但每个顶点可以访问多次。
浏览 5提问于2021-10-29得票数 1
1回答
应用网络流
、、、、
因此，我最近开始研究网络流(最大流、最小切分等)，而网络流的一般问题总是涉及将某物的"n“赋值给另一件事物的"k”。例如，我如何在一个有"k“学校的城市里为"n”儿童建立一个网络流，使孩子们的家离学校只有x公里(简单地说，我们可以说是1公里)？
如果我要进一步增加限制，例如，假设每所学校不能有100多名学生呢？有人能帮我解决我最初如何设置我的算法来处理这样的问题(也会感谢任何参考)吗？他们往往在期中考试时出现，所
浏览 0提问于2018-11-05得票数 0
回答已采纳
1回答
我很想用网络流的方法来解决这个问题。希望这里有人能花点时间帮我构造一个适合这个问题的图表。构造的图，当求出最大流量时，将导致给定机器数和作业计划的作业数量最大化。给定m个机器和n个作业，约束m个≤n，用网络流算法求解在给定机器数下作业数最大化的分配问题。我尝试过的方法：->
浏览 1提问于2015-05-27得票数 2
1回答
你能推荐一种算法来确保总行驶距离最小吗？(即每名学生离考试中心的距离之和)
显然，i-can-hold1+i-can-hold2+...
浏览 2提问于2012-11-24得票数 1
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
腾讯会议
云直播
对象存储活动推荐
腾讯云开发者
