标题也许还不清楚，但我会在这里解释得更好：
假设我们有一个有向加权图G，具有N个节点和K个边。
有两个主要节点:节点1和节点N。我们的主要目标是从1到N，通常从1到N有多种可能的路径。
我们也有M个人想从1到N旅行。
每条边都有一个重量w。重量意味着有多少人可以同时通过这个边。
每一条边缘都可以想象成一条路，那需要一天的时间。
我们要做的是让M人从节点1到节点N，将天数最小化。
例如：
在这个图中，如果我们有3个人通过，最少的天数是2。我们把2个人传递给节点2，1人传递到节点3，2人将花费2天的时间到达节点3，1人将花费1天的时间到达节点3。
我的问题是:如何解决
浏览 5提问于2022-06-15得票数 0
我不知道该用什么术语来搜索(我已经搜索过“映射算法”和“一对一算法”)，我想不出一个更简单(更规范)的公式。
我有两套，比如说
A B C D E
和
L M N O P
给我一张一对多的地图。
A --> L, M, N, P
B --> M
C --> M, N, O
D --> N
E --> O, L
什么是最简单和/或最快的算法，它可以告诉地图的一个一对一的“子集”是否可以覆盖所有的项目？例如，上面确实存在这样一个“子集”：
A --> P
B --> M
C --> O
D --> N
E --> L
我不需要知道子集映射
浏览 9提问于2013-01-22得票数 2
回答已采纳
2回答
问题
给出了一个简单的无向图G= (V，E)，其中x-V=n=节点数，x-E=m=m=边数，检验G是否三连通.也就是说，在随机删除任意两个边后，G是否保持连通(从每个节点到所有其他节点存在一条路径)。所需时间复杂度: O(n^2(n + m))
我的解决方案
对于G中的每个节点，执行以下操作：
检查节点是否至少有3条边缘到3个不同的节点: O(1)。
忽略节点并运行深度优先搜索剩余的图，以检查它是否仍然连接: O(n + m)
时间复杂度: O(n(n + m)) = O(n^2(n + m))。
我的解决方案正确吗？
浏览 3提问于2019-09-13得票数 1
回答已采纳
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回答
我试着解决了一个关于的问题。我有一个源和两个水槽。我需要在这个网络中找到最大流量。这部分是一般的最大流量.然而，在这个特殊版本的最大流问题中，两个目标必须得到相同的流量。
有人能帮我吗?我该怎么做？
浏览 6提问于2014-01-21得票数 6
回答已采纳
1回答
最大流边约束
、、
如何解决最大流问题，其中图中的一些边必须有一个flow = 3n，其中n是一个非负整数？换句话说，如何施加某些边必须具有可被3除的流的约束？例如，这些边可能有0，3，6，9.但可能没有流动1，2，4，5.理想情况下，我想要一种方法来计算这样的图上的最大流，以及最大流配置中每个边上的流。
浏览 3提问于2015-10-16得票数 1
回答已采纳
1回答
找到最大匹配
、、
设G(A,B,V)，一个二分图，其中|A|=|B|=n.有一个匹配的，M子集的E，其中|M| = n-2013。描述一个有效的算法，以确定是否存在最大匹配。
基本上，给定的解决方案是通过添加s,t顶点，将s连接到A中的每个顶点v，将B中的每个顶点v连接到t，从而从图中构建一个流网络。所有容量均为1。
现在，我们给出了所有边M (以及从s和t连接到M边的所有边)的起始流。
现在，我们只需要运行折叠-Falkerson(或Edmond)算法，并检查我们是否能够改进2013路径(即为某些路径添加更多的流)。更准确地说，我们最多需要运行BFS， 2013 times来决定。
我的问题是：
为什
浏览 5提问于2016-09-13得票数 1
回答已采纳
2回答
我已经计算了最大流量使用福特富尔克森算法，现在我想实现的项目选择问题，我需要计算的最大。不是的。我需要找到一个包含no的min.cut。最大利润的可行项目。应该是什么算法才能找到一分钟。在了解了图中的max.flow之后。*如何使用最大流来确定包含no的切分。为最大流量做出贡献的节点，我需要选择最优的节点集，以使收益最大化。在我的应用程序中，每个节点都与收入相关，它也可以是正负的。而且还有优先级约束，eg.if a比b&c还必须选择，有人能告诉我如何实现吗？
我在最大流图中对其进行了如下转换:如果收入(节点)>0，则从源->节点添加边缘，从节点->接收器添加边缘，并
浏览 3提问于2012-07-06得票数 2
回答已采纳
5回答
二部匹配
、、、、
如何用C或C++实现二部匹配算法(可能基于最大流算法)？
具体地说，我在一个文件中有这个输入：(1,3) (1,5) (2,5)
(M，F) -->其中M表示男性的id，F表示女性的id。
我需要找到匹配的最大数量，并显示匹配的情侣。喜欢:匹配: 1&3，2&5
我在一些书中读到过，我可以基于“网络中的最大流量”算法来解决这个问题，但除了“这个问题可以通过...算法解决”这句话之外，我找不到任何具体的信息。我对max-flow知之甚少，也不知道如何实现它……
浏览 1提问于2009-05-18得票数 1
回答已采纳
在下面的最大流问题中，算法首先可以选择S-A-D-T路径。在这种情况下，算法将不再看到任何增强路径，因此它将生成4作为最大流的答案。但是，如果算法首先选择任何其他路径，则会看到最大流变为5。
浏览 11提问于2021-12-04得票数 0
1回答
给定一个参数k，我试图从有向图中删除k个边，这样最大流就会尽可能地减少。这个图有一个源和一个接收器t，每个边的容量是一个。图可能包含循环，也可能不包含循环。
我建议的解决方案是首先对图执行拓扑排序，使用“宽恕”循环的算法--也许是通过忽略将我们带回源的边缘。然后(假设k >= 1)：
i = 0
for each vertex u order by topological(u)
for each edge (u, v) order by topological(v) descending
if topological(v) > topological(u) th
浏览 7提问于2010-04-11得票数 2
回答已采纳
2回答
最大流量算法运行时间
、、、
我有以下两个问题。
正确或错误:在Ford-Fulkerson算法中，我们总是可以找到一个增强s路径的流序列，这样我们就可以在多项式迭代次数中达到最大流。
正确或错误:我们总是可以在Fulkerson算法中找到一个增强s路径的流序列，这样我们只有经过指数型迭代才能达到最大流。
浏览 4提问于2018-12-18得票数 3
1回答
非赋权图中的最大流
、、、
最大流问题通常采用edmond-karp算法来解决，该算法建立残差图，并利用BFS来寻找增广路径。
但最大流问题通常是针对赋权图定义的。对于未加权的图，我们可以简单地将每条边的权重视为1，但我想知道是否有更简单的算法来解决未加权的版本。
浏览 4提问于2017-02-22得票数 4
1回答
我正在阅读Robert Sedgewick的算法第二卷。这一部分来自网络流量算法。
我在理解下面提到的流分解定理及其推论时遇到了困难。
流分解定理:任何循环都可以表示为沿一组至多E方向的边的流。
推论1:任何st-网络都有一个最大流，使得由非零值诱导的子图是无圈的。
推论2:任何st-网络都有一个最大流，它可以表示为从s到t的至多E条有向路径的流。
请用一个简单的例子帮助我理解上面的定理和推论，谢谢！
浏览 3提问于2012-05-14得票数 1
2回答
全对最大流
、、
给定有向加权图，如何求出所有顶点对之间的最大流(或最小边切)。
天真的方法是简单地为每对调用一个像Dinic这样的最大流算法，其复杂性是O((V^2)*E)。
因此，对于所有对，它都是O((V^4)*E)。
是否可以通过一些优化来降低O((V^3)*E)或O(V^3)的复杂性？
浏览 4提问于2012-12-21得票数 8
2回答
顶点容量无约化的最大流
、、、
除了edge的功能之外，我还在尝试实现顶点容量的最大流。我在wiki中发现了一个新的图G，其中每个顶点对应于v_in和v_out，并对边进行了适当的更改。
我最初的实现做了一些其他的事情，我想知道它是否错误。
在最初的fulkerson检查路径的步骤中，它增加了路径相对于这条路径中最小容量的边缘的流量(我们不能超过这一点)。如果我也在这条路径中找到了最小的顶点容量，那么会怎样呢? --这些量之间的最大值(max(b(v)) and max(b(e)) for v and e in path p) --将定义可以通过该路径的最大流，不是吗？复杂性保持不变。
浏览 13提问于2022-08-23得票数 1
1回答
将分配问题转化为最大流问题
、、、、
根据我在这个链接中读到的，在一定的条件下，分配问题可以转化为一个最大流问题。我知道最小成本流问题的转换，但是我想从这个方法中知道在什么条件下这个问题变成了最大流问题？
浏览 7提问于2021-06-05得票数 1
回答已采纳
1回答
二部图的最大基数
、、、
是二分图中的最大基数，与该图中的最大流相同，其中两个虚拟节点为源，另一个为接收器。
源连接到一组二部图，另一组连接到接收器。
浏览 3提问于2014-09-23得票数 0
回答已采纳
1回答
我读过很多文章，指出用最大流算法可以找到二部图的最大匹配。但是，我们从最大流得到的匹配可能不是最大的，或者匹配没有最大的边。
来自Anti Laaksonen的竞争性方案编制手册的例子：
但是，如果我以不同的方式呈现这个图，那么现在的图形是：
然后，随着最大流量算法的推进，匹配结果为1-5，2-7。
因为1简单地擦除了通向水槽的路径，但是如果它被移到边缘1-6，那么匹配可能是
1
浏览 3提问于2021-06-24得票数 1
回答已采纳
1回答
图的匹配算法
、、、
如果有一定数量的节点与边缘连接(如与街道交叉)，且每个节点的值为0到3，则边的值为0。
现在我想写一个算法，它将节点的值分配给值边，所以在算法终止后，所有节点的值都是0，而所有的边都是<= 1。
例如，给定此图表：
我想制作这个：
。
我的解决方案：
我已经定义了数据类型-十字路口和Street：
public class Crossing{
int value;
}
public class Street{
int value;
Crossing A, B;
}
该算法迭代交叉路口并将值分配给街道(注意，交叉口只能将其值分配给相邻的街道)。
v
浏览 3提问于2017-07-11得票数 1
回答已采纳
1回答
我正在尝试确定最佳的算法来解决一个分配课程的要求。要求有一定数量的学分，才能被视为满足。课程有很多学分，当被录取的时候。因此，数据结构看起来类似于：
export class Course {
constructor(public id:number,
public credits:number) {
}
}
export class Requirement {
constructor(public id:number,
public name:string,
public credits:nu
浏览 5提问于2016-07-06得票数 2
回答已采纳
目前，我正在尝试创建一个程序，该程序在与公共源节点边缘必须具有相同流的约束下，通过网络查找最大流。我遇到困难的就是这个约束。
目前，我有获得所有流增强路由的代码，但我不太愿意编写增强代码，因为我不知道如何添加约束。我正在考虑一种回溯算法，它尝试使用Fulkerson方法分配流，然后尝试调整以适应约束。
所以我的密码是：
有一个图类，它具有所有顶点和边的属性，以及获取顶点的入射边和顶点的前面的边的方法：
class WeightedEdge:
def __init__(self, from_vertex, to_vertex, capacity):
self.tail =
浏览 9提问于2021-06-09得票数 0
1回答
一段时间前，我读到了一个通用的最小切割算法，它将一个图作为输入，并删除一个min。使两个断开的组件保持不变的边数。
我现在正在处理一个具有10k+节点和500k+边的无向图(两个顶点之间没有多条边)。为了给节点之间的交互赋值，我考虑计算两个给定顶点的最小割断开(或流相关的度量)。
有没有有效的算法来得到一个值(最小值的基数。对于图中的每一对顶点)？作为这个主题的新手，如果有人能提供论文或其他资源的链接，概述在合理的运行时复杂性运行的算法，我将不胜感激。
谢谢!
浏览 1提问于2012-02-21得票数 8
回答已采纳
我有一个无向图，想要计算两个顶点之间可能的最长路径，其中每条边只能访问一次，但每个顶点可以访问多次。
我在JTGraph中找到的所有最长路径解决方案都是在每个顶点只访问一次的前提下运行的。
浏览 5提问于2021-10-29得票数 1
3回答
考虑到在具有整数弧容量的有向网络中，我们有一个非整数最大流.
是否有一种算法可以将此流转换为整数最大流？
它的运行时间是多少？
这不是家庭作业问题。
浏览 9提问于2011-04-18得票数 1
再重复一下这个问题:我们有一个流程图G，具有整数容量。我们能否找到一个最大流，其中至少有一条边，e，我们的f(e)等于非整数？
当我第一次尝试它的时候，我有点忽略了它，并认为这违反了完整性定理，因此它是错误的，但仔细阅读之后，我发现它没有违反任何规则。显然这是真的。
我一直在尝试画一个简单的例子来获得可视化效果，但我似乎想不出任何东西。有没有人能给我看一个流程图的例子？
浏览 3提问于2016-11-24得票数 3
1回答
二部图的优化
、、、
有两组，一组包含类列表，另一组包含teachers.Each列表，教师有一组classes.We必须为某一特定类指定一名教师，这样一种方法使得教师所占用的班级数应该是maximum.Is，这个问题与任何优化算法有关?我找不到任何类似的algorithms.Please帮助我得到逻辑。
感谢平面语
浏览 1提问于2013-11-18得票数 1
回答已采纳
1回答
唯一的最大流算法
、、
如何检查图网络是否包含唯一的最大流？有没有什么多项式时间的算法可以做到这一点？谢谢!
编辑:查找源和目标之间的所有切割。对于每个切割，如果有两条边具有最小容量，则最大值不可能是唯一的。返回false。如果所有剪切都有一个最小容量，则返回true。但我需要一个更有效的算法。
edit2:我需要知道图网络是否有唯一的最大流(我只能以一种方式将最大流从源发送到汇点)。
浏览 2提问于2013-12-31得票数 2
我“找到”了一个在无向图中寻找最大流的算法，我认为这个算法是不正确的，但我找不到我的错误。这是我的算法:我们以如下方式构造一个新的有向图:对于每条边${u，v}$，我们创建边$(u，v)$和$(v，u)$，其中$c((u，v))=c((v，u))=c({u，v})$。然后我们将Ford-Falkerson算法应用于新图。现在我们用下面的方法在第一个图中做一个流:让我们$f((u，v))\ge f((v，u))$，然后我们将边${u，v}$从$u$指向$v$，并取$f'((u，v))=f((u，v))-f((v，u))$。现在它将是我们的无向图的最大流，因为否则我们将为相应的有向图构造一
浏览 4提问于2014-11-13得票数 1
1回答
问题是给定一个加权边双向图，找出边的集合，通过删除给定的一组节点彼此断开连接的边。而且这些边权重的和也应该是最小的。这个问题有什么名字吗？有没有什么特别的算法来解决它们？我知道这一定是NP完全问题。
浏览 1提问于2012-04-27得票数 1
回答已采纳
1回答
我被要求为以下问题开发一个算法：
给予：
A流网络G，其边的最大容量为1G的最大流f_x_xa正整数K_。
完全删除K边，使网络流最小化。
我的想法/算法：
，如果K大于或等于max，删除所有穿过G的最小割集的边，如果K仍然大于零，删除随机边，并且新的最大流是零
，如果K等于\F，删除所有与G的最小切分相交的边，新的最大流为零
如果K小于，则删除与G最小割集相关的边的K，且新的最大流为delete 。
我需要一些验证，因为最大流量/Min削减是新的我。最后，我得到的最大流/最小值切割背后的直觉是，Min (Source，Sink)剪切作为一个"bottleneck"工作到我们可
浏览 0提问于2020-06-21得票数 0
回答已采纳
2回答
用Ei表示索引为i的边。
设S是一个解的数组。如果最大流包含Ei，则Si = 1。否则，Si = 0。
我想得到一个最大流，它的解按字母顺序是最小的。我可以使用Ford-Fulkerson获得最大流量，但我不知道如何才能获得按字母顺序排序的最小解。
浏览 4提问于2014-11-14得票数 0
3回答
动态图中的最大流
、、
我正在寻找快速算法来计算动态图中的最大流量(添加/删除具有相关边的节点到图中)。也就是说，我们在G中有了最大流，现在添加/删除了带有相关边的新节点，我不喜欢重新计算新图的最大流，实际上，我想使用以前的结果来计算这个图。
任何不占用大量时间/内存的预处理都会被占用。
最简单的想法是重新计算流程。
另一个简单的想法是，保存之前的最大流量计算中使用的所有增加路径，现在为了添加顶点v，我们可以找到简单的路径(在上一步更新的容量图中)，这些路径从源开始，到达v，然后到达目的地，但问题是这条路径应该很简单，对于这种情况，我找不到比O(n*E)更好的路径。(如果只有一条路径或者路径是不相交的，这可以在O(n
浏览 0提问于2012-01-26得票数 10
回答已采纳
1回答
我正在做一个个人项目，遇到了一个障碍。我不会确切地说明问题的原样，因为很难解释，相反，我将提出一个类似的问题，我相信这个问题可以和我的实际问题一样得到解决。
假设:您有3个项目(A、B和C)，而这些项目只能在特定的框(1、2或3)中使用。每个项目可以放置在0或更多的盒子内。例如，假设这些项目可以放置在这些框中：
A项可以放在方框1或2中。
B项只能放在方框2中。
C项只能放在方框3中。
这样做的目的是找出一个解决方案是否存在(而不是解决方案本身)，其中所有的项目都可以放在一个盒子里，而一个盒子只能容纳一个项目。例如，上述示例的一个可能的解决方案可以是项目A -> Bo
浏览 0提问于2017-08-24得票数 0
回答已采纳
1回答
我正在寻找一个算法，以找到一个无向图的全局小割集。我想输入一个图和算法输出最小的边数，通过切割它们，可以将给定的图分成两部分。
以下是要求：
找出准确的边缘，而不仅仅是它们的数量。
最小切边应100%正确计算.
这是一个无向图。
算法应通过指示已找到答案或未找到答案而终止。
我在网上搜索了一些文章，发现Karger的最小割集算法是随机的，它的输出可能不是精确的最小割集。我可不这么演算法。我想要计算精确的边(我需要知道它们是哪些边)，它的数目是最小的。
我想听听一些建议，而我正在寻找这样的算法。如果您的建议附带了示例代码的算法介绍，那就太好了。
提前谢谢。
浏览 6提问于2016-03-16得票数 0
2回答
添加边缘后更新最大流
、、、、
考虑到我们有一个网络流，并且使用Edmond算法，我们已经有了网络上的最大流。现在，如果我们在网络中添加一个任意的边缘(具有一定的容量)，那么更新最大流量的最佳方法是什么？我正在考虑更新关于新的边缘的剩余网络，并再次寻找增强路径，直到我们找到新的最大流量，但我不确定它是否工作或它是否是最好的方式！
浏览 6提问于2014-12-13得票数 4
回答已采纳
1回答
我知道这个问题在这里已经讨论过不止一次了。但是，我需要在运行时间为|V| x |E|的有向图中找到顶点不相交路径的最大数量K。
我知道将每个顶点转换为v_in，v_out，然后从v_in到v_out添加容量为1的边，并为每一对顶点(u，v)添加容量为1的边从u_out到v_in的算法，然后计算此网络中的最大流量。然而，在我的计算之后，这个算法对于最大流量需要O(E)预处理+ O(VE^2)或O(V^2E)。我做错了什么吗？
浏览 4提问于2018-03-13得票数 0
我不知道怎么写这个问题的标题。现有的标题可能不准确。
以下是问题所在：
我有m组(数组)，比如说，4个组。每个组包含一些数字。我们希望每个组给出一个数字，最终得到的4个数字(每个来自一个组)是不同的。
现在，鉴于这四个小组，我如何确保他们符合我们的愿望？
例如,
A: 0，2，3
B: 0，2
C: 2，3
D: 1
以上四组都符合我们的愿望。D给1，C给3，B给2，A给0。
但是如果
答:2
B: 2
C: 2，3
D: 1
都是坏的。我们不能让每个小组都给出一个不同的数字。
我的想法是最愚蠢的方法，我只是回溯所有的元素，从所有的组，得到每一个元素的组合，并看到这些元素从一个组合是不同
浏览 3提问于2012-06-13得票数 2
回答已采纳
我试图通过阅读Klienberg和Tardos的书来理解网络流。我对理解以下术语以及这些术语的价值如何在我们进行增强时发生变化有疑问。到目前为止，这是我所理解的。如果这是错误的，请纠正我。
s-t flow --这是一个随机路径P，可以在任何图形G中找到，以将流从s传送到t。
值--这表示源生成的流的数量。
最大流量-这是我遇到问题的地方。我无法理解流的值与最大流之间的区别。最大流是表示特定图形s-t路径中能够承载流量的所有s-t路径之和，还是表示这些s-t路径中的最大值？
这里的任何帮助都将不胜感激。谢谢
浏览 3提问于2015-11-26得票数 1
回答已采纳
1回答
我正在实现最小割集图聚类，并且我需要能够将一个图分成两个部分-- S和T，根据在每个聚类步骤上构建的针对的和t顶点的st min裁剪。基本上，我希望有一个函数，它接受图G、节点s和节点t，并返回两个不相交的节点集S和T<code>E 217</code>。
据我所知，找到最小流量的最简单方法是利用最小切割~最大流量对偶，并使用推挽算法进行最大流量计算。但是推挽算法并没有给我们任何关于、S、和T集的信息。
那么，获得S和T最小剪切子集的正确方法是什么？有一种方法可以使用推挽算法吗？这在C++或Python中有实现吗？
浏览 6提问于2013-07-16得票数 1
1回答
如果你有一个国家完整的公交时间表，你怎么能在一天内在两个指定的车站之间找到最多的乘客数？
我假设公交时刻表给出了每个公共汽车站的出发时间和到达时间的完整清单，以及每辆巴士的容量。在这个问题上，你得到了开始和结束的停止。
您可以确定给目的地提供最短时间的公共汽车序列，并填满所有从一开始就沿着这条路径出发的公共汽车，然后当每辆公共汽车到达一个车站时，只需将尽可能多的乘客换乘下一辆即将离开的公共汽车。然而，没有理由认为这应该具有最大的容量。
这个问题最快能解决的是什么？例如，假设对于M个城市，我总共有N条记录；路由记录Rᵢ包含一个数字Kᵢ、容量Cᵢ以及Kᵢ城市号、Kᵢ到达时间和Kᵢ出发时间的
浏览 2提问于2013-07-08得票数 5
回答已采纳
1回答
在这里，我试图断开一个图中的两个顶点，并尽可能减少边缘去除。
在两个顶点A和Z之间的图中，您可以从许多方面找到答案。以最佳的方式，您可以从A删除一个边缘到B。
如果有什么具体的算法吗？
本文提出了用最大流最小切问题来解决这一问题的一些建议，但还没有得到将这个问题转化为最大流最小切定理的一般想法。在这个过程中，我可能最终会删除F和G之间的一个边缘，这是无用的。
浏览 0提问于2016-05-08得票数 12
回答已采纳
1回答
如果我想在无向图中找到最大流，我该怎么做呢？
在维基百科的页面上，它说算法需要有向图(我只会把每条边转换成一对边)，但问题是我可能有非整数的权重(例如0.5)。
有没有适合这个问题的现有算法？
浏览 4提问于2013-04-25得票数 0
回答已采纳
2回答
是否有一个确定性的算法来检查一个图是否包含一个从源到目的地的顶点不相交的路径，具有复杂性O(nm^2) (n是顶点数，m是边数)，还是这个NP-硬(如果是，为什么)？顶点不相交路径是指没有公共内部顶点的路径。例如：
s -> a -> b -> c -> d
s -> x -> y -> z -> d
是顶点不相交但是
s -> a -> b -> c -> d
s -> x -> a -> z -> d
^
因为a是普通的顶点。
问题是：
浏览 4提问于2013-05-01得票数 2
回答已采纳
2回答
我有一个网络，可能是这样的：
基本上，我想知道如果移除/禁用，可以断开源极和漏极的最小绿色圆圈数。(在本例中为1)
我已经成功地实现了Edmonds-Karp算法，但我不知道如何用有向边来建模网络，所以我得到了想要的结果。
如果我只是将节点之间的每个连接替换为容量为1的两条相反的有向边，我使用EdmondsKarp得到的最大流量为2，但我只需要删除1个绿色圆圈就可以断开网络。
如何将我的网络建模为节点和定向边缘？
浏览 6提问于2010-11-17得票数 5
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
