我们也有M个人想从1到N旅行。
例如：
在这个图中，如果我们有3个人通过，最少的天数是2。是最大流吗？如果是的话，如何建模这个问题，以便它可以解决的最大流量？
浏览 5提问于2022-06-15得票数 0
5回答
二部匹配
、、、、
如何用C或C++实现二部匹配算法(可能基于最大流算法)？(M，F) -->其中M表示男性的id，F表示女性的id。喜欢:匹配: 1&3，2&5
我在一些书中读到过，我可以基于“网络中的最大流量”算法来解决这个问题，但除了“这个问题可以通过...算法解决”这句话之外，我找不到任何具体的信息。
浏览 1提问于2009-05-18得票数 1
回答已采纳
2回答
问题是：
设G= (V，E)是具有m条边的n个>= 3个顶点的有向图。顶点集v包括三个特殊的顶点a，v和b。找到一条从a到b的简单路径，如果存在的话。(简单路径是没有重复顶点的路径。)我相信这个问题应该/可以用最大流量算法来解决，但我不确定如何解决。这让我想起了一个多源的最大流量算法，其中边的容量为1。有人知道如何将问题简化为最大流量算法吗？
浏览 0提问于2012-01-05得票数 8
1回答
据我所知，找到最小流量的最简单方法是利用最小切割~最大流量对偶，并使用推挽算法进行最大流量计算。但是推挽算法并没有给我们任何关于、S、和T集的信息。
那么，获得S和T最小剪切子集的正确方法是什么？有一种方法可以使用推挽算法吗？这在C++或Python中有实现吗？
浏览 6提问于2013-07-16得票数 1
在下面的最大流问题中，算法首先可以选择S-A-D-T路径。在这种情况下，算法将不再看到任何增强路径，因此它将生成4作为最大流的答案。但是，如果算法首先选择任何其他路径，则会看到最大流变为5。
浏览 11提问于2021-12-04得票数 0
1回答
请给出几种无向图最小割集的确定性算法，以及它们的复杂度。(顺便说一句，我知道福特-富尔克森算法有一个无向版本，它为每个有向边缘增加了一个相反的平行边，有人能告诉我这个算法的时间复杂度是多少，或许可以给我更多的参考？)
谢谢。
浏览 7提问于2015-09-16得票数 2
福特-富尔克森算法会在O(mn)时间内找到具有n顶点和m边的单位容量流网络(所有边都有单位容量)的最大流吗？
浏览 8提问于2015-11-06得票数 7
回答已采纳
1回答
我很难理解某些逻辑。我有一个二部图如下所示。我希望找到最优匹配的所有顶点在左侧(Viz，A1，A2，A3，A4)。我从朋友那里得到了一个建议，那就是边权之和可以用来解决这个问题。不过，我不知道，在这种情况下，边权之和会有什么帮助。例如，对于A1，我可以说AL2是最好的匹配，依此类推。然而，我的朋友建议，边缘权重是这个问题的最优解决方案。我无法理解如何才能成为最佳解决方案。他的想法是，所有的(A1，A2，A3，A4)都将连接到所有的(AL1，AL2，.，AL6)，对于每个边，我们将计算边权的总和。有人能帮我理解他的真正意思吗？
编辑:我认为这可能不是二分图中完美匹配的情况，因为左边的
浏览 5提问于2013-09-19得票数 0
回答已采纳
在最大流问题中，当我应用ford-fulkerson算法寻找最大流时，如果图的所有链接都有权重1，则最大流将是我在ford fulkerson算法中找到的路径数，对吗？我是说，dfs路径的数目。
浏览 4提问于2014-04-17得票数 1
回答已采纳
1回答
我修改了最大流量问题的任务。我应该找到满足条件的最小流(其中f是流，c是容量)：因此，在每一个边缘的流动至少是边的容量。我有函数MaxFlow，它给了我经典的最大流，我可以调用它一次。
有人能帮我做伪算法吗？我正在考虑修改福特-福尔克斯算法，并根据我的需要改变它，但我不知道哪里适合那个MaxFlow？当我知道图中的最大流时，它如何帮助我处理算法？谢谢
浏览 0提问于2014-05-12得票数 1
回答已采纳
1回答
我被要求为以下问题开发一个算法：A流网络G，其边的最大容量为1G的最大流f_x_xa正整数K_。，如果K大于或等于max，删除所有穿过G的最小割集的边，如果K仍然大于零，删除随机边，并且新的最大流是零如果K小于，则删除与G最小割集相关的边的K，且新的最大流为delete 。我需要一些验证，因为最大流量/Min削减是新的我。最
浏览 0提问于2020-06-21得票数 0
回答已采纳
3回答
动态图中的最大流
、、
我正在寻找快速算法来计算动态图中的最大流量(添加/删除具有相关边的节点到图中)。也就是说，我们在G中有了最大流，现在添加/删除了带有相关边的新节点，我不喜欢重新计算新图的最大流，实际上，我想使用以前的结果来计算这个图。
任何不占用大量时间/内存的预处理都会被占用。最简单的想法是重新计算流程。另一个简单的想法是，保存之前的最大流量计算中使用的所有增加路径，现在为了添加顶点v，我们可以找到简单的路径(在上一步更新的容量图中)，这些路径从源开始，到达v，然后到达目
浏览 0提问于2012-01-26得票数 10
回答已采纳
1回答
我需要在这个网络中找到最大流量。这部分是一般的最大流量.然而，在这个特殊版本的最大流问题中，两个目标必须得到相同的流量。
有人能帮我吗?我该怎么做？
浏览 6提问于2014-01-21得票数 6
回答已采纳
嗨，我很难用学习福特-富尔克森算法.然而，看到视频，这让我很困惑。这位讲师说，根据福特-富尔克森算法，最大流量为19，但我无法用19的费用找到任何削减。怎么了？
浏览 2提问于2018-12-02得票数 3
回答已采纳
1回答
找到最大匹配
、、
设G(A,B,V)，一个二分图，其中|A|=|B|=n.有一个匹配的，M子集的E，其中|M| = n-2013。描述一个有效的算法，以确定是否存在最大匹配。现在，我们给出了所有边M (以及从s和t连接到M边的所有边)的起始流。现在，我们只需要运行折叠-Falkerson(或Edmond)算法，并检查我们是否能够改进2013路径(即为某些路径添加更多的流)。更准确地说，我们最多需要运行BFS， 2013 times来决定。在我看来，M只是一个任意的匹配。就像我们假设<em
浏览 5提问于2016-09-13得票数 1
回答已采纳
6回答
我一直在读关于流网络的文章，但我所能找到的都是最大流算法，如Ford-Fulkerson，push-relabel等。给定最大流-最小割集定理，是否可以使用这些算法中的一种来使用最大流算法在图上找到最小割集？多么?
到目前为止，我找到的最好的信息是，如果我找到“饱和”边，即流量等于容量的边，这些边对应于最小切割。
浏览 6提问于2010-12-19得票数 59
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
