max-flow

1热度

1回答

我有一个有27000个弧的定向网络，每个都有一个重量。随着代码： G=nx.Graph(G) nx.maximum_flow(G,'CHN',"CHL") 我得到的错误： NetworkXUnbounded: Infinite capacity path, flow unbounded above. 有谁知道如何获得最大流量值？顺便说一句，当我运行：G.edges(data=True)，

2热度

2回答

贪婪的最大流量

该用餐问题：几个家庭一起出去吃晚饭。为了增加他们的社交互动，他们想坐在餐桌旁，以便同一个家庭中没有两个成员在同一个桌子上。假设晚餐队伍有p家庭，并且i家庭拥有a(i)成员。此外，假设有q表格可用，并且j表格的座位容量为b(j)。问题是：我们可以坐在桌子上的人数最多是多少？编辑：这个问题可以解决，创建一个图形和运行最大流量算法。但如果我们有2 * 10^3顶点的Dinic算法，则全局复杂度

0热度

1回答

Java MaxFlow算法，产生边缘故障

我试图解决最大流量问题，图中有无限的加权边，但每个节点都有一个容量。我使用ford fulkerson算法解决了这个问题，并将每个节点分成一个in节点和out节点，容量是两者之间的加权边。当我在边缘进行硬编码时（请参阅代码中的注释块），我的算法效果很好，但是当我尝试从文本文件构建边缘时总是返回零。对于我的生活，我无法弄清楚为什么，我已经检查过，以确保所有的边缘都正确构造，并且不知道什么是错的。（

0热度

1回答

USACO牛栏障碍：Dinic的算法/改变为未注册的指针

声明：并非我用来试图解决问题的所有代码都需要回答我的问题，但如果需要，我会提供其余的代码。问题（如果上下文被需要）：http://www.usaco.org/index.php?page=viewproblem2&cpid=93 #include <iostream> #include <stdio.h> #include <stdlib.h> #include <vector> #in

1热度

1回答

什么是节点不相交路径？

我需要解释一下哪些节点不相交的路径？以及如何确定有向图中两个节点Source（s）和Sink（t）之间的节点不相交路径的最大数量。任何人都可以用图形来解释。

5热度

1回答

闽成本最大流用的boost :: successive_shortest_path_nonnegative_weights

我需要使用的BGL提供的 boost::successive_shortest_path_nonnegative_weights() 函数来计算最小成本最大流的流网络（V 1_60_0）。如documentation指定， the directed graph G=(V,E) that represents the network must be augmented to include t

1热度

1回答

如何使用Dinic的算法在无向图中找到最小切割边缘？

我正在寻找一个算法，当一个给定的两个节点的'和'在一个未经过训练的图中，找到最小切割边缘，它将图形分成两个A和B'''将在A和“T”将在B. 我看大多数人提示了福特Fulkerson算法，以用于该任务，在here。我在想，可以使用Dinic的算法。由于Dinic的算法可以通过动态树加快速度。因为我想以最快的方式找到最小切割边缘。哪种算法更快找到一个巨大的无向图中最小切割边缘？我希望听到一些建议

0热度

2回答

是否有可能与给定的成本出售的所有项目，以人

最近，我遇到了一个真正的问题，我可以refolmulate为以下算法任务的钱给量：问题：给定一组N个人，每个人都有一定数额的金钱和一套M物品，每个物品都有一定的成本，是否有可能出售所有物品？每件商品最多只能由一个人购买，每个人可以购买多件商品，以使其成本不超过他所拥有的金额。我尝试的解决方案：我想构建一个网络，找到一个最大流这样的方向： - 使对应于人的一部分与顶点的bipartide图

1热度

1回答

最小流量，不满足所有需求

我使用NetworkX来解决具有多个源和汇的最大流量问题。我发现一个在NetworkX中运行得相当好的函数叫做max_cost_flow，但是我遇到的问题是它要求净需求为零，换句话说，没有接收器应该小于它的需要，否则会引发错误。我可以使用什么（或者我怎样才能修改这个算法）来允许它计算出最佳可能流量，而不一定满足所有条件？每kraskevich的建议： import networkx as nx

1热度

2回答

如何从另一个类调用函数，其中函数使用局部变量

我有两个类MaxFlow和MinMaxFlow。 MaxFlow使用升压图从网络拓扑创建一个图表： class MaxFlow { public: MaxFlow : g_() { createGraph(); } //constructor void createGraph(); void modifyGraph(); // modify the graph to