algorithm - 网络流算法

Question

我有这样的问题:

我们得到了一个二分图。例如

A1 B1
A2 B2
A3 B3
A4

这是邻接表表示(假设图是双向的)

B1 -> A2, A3
B2 -> A2, A3, A4
B3 -> A1

最终结果应该是左侧 (As) 中的所有节点都恰好有 1 个传入边，同时 - 我们需要最小化需要从各个 Bs 节点传出的最大边数。在这种情况下，答案是:

B3 can connect to A1
B2 can connect to A2, A4
B1 can connect to A3

所以这里需要从单个 Bs 节点引出的最大边数是 2。我们不能覆盖所有 A，同时让 B 节点没有 2 条边引出它来覆盖 A。

另一个例子:

A1 B1
A2 B2
A3 B3
A4 B4

B1 -> A1, A2, A3
B2 -> A1, A2, A3, A4
B3 -> A1, A2, A3
B4 -> A1, A2, A3

在这种情况下，答案是:

B1 can connect to A1
B2 can connect to A4
B3 can connect to A3
B2 can connect to A2

这样我们将一次覆盖所有的 A，同时我们已经最小化了需要从单个 B 出来的边的最大数量。所以这里单个Bs节点需要出边的最大数量为1。

另一个例子:

A1 B1
A2 B2
A3 B3
A4
A5
A6

B1 -> A6
B2 -> A1, A2, A3, A4, A5
B3 -> 

在这种情况下，答案将是 5，即需要从单个 B 中走出的边的最大数量是 5。不能少于此数量。

我已经实现了基本的 ford fulkerson 算法，我知道这也是网络流，但不知道如何与之相关。

如果有人能给出一些关于图表的提示，那就太好了。

谢谢

Answer 1

找到一个最优解——所有 B 最多有一个出边(如果存在的话)很简单:

• 向图中添加源和汇。来源将有一个到 B 列表中所有顶点的容量为 1 的边。
• 所有 (B,A)边的容量为 1。
• 所有 A 都将有一个容量为 1 的出边到汇点。
• 现在，运行流算法将产生最大数量的A 中的顶点可以被每个 B 覆盖，只有一个出边(最佳解决方案，如果存在的话)

---

编辑:

现在，基于上述想法，并且由于您正在尝试最小化从单个 B 到 A 的最大边数(而不是它们的总数，正如我之前所想的那样) ，最佳解决方案很简单:

while there is no coverage:
   set capacity(source,b_k) = increase_size() (for each b_k in B)
   run max flow algorithm on the graph suggested above
return last flow found

复杂度是 O(E*V*#iterations) (在这个问题中 f <= V ，因此如果 ford-fulkerson 的复杂度是 O(EV) )，其中 #iterations可以在您寻找的最小最大数量中线性完成，或者使用指数增加，然后在范围内进行二进制搜索(如 Evkeny Kluev 所建议的)，记录该数字。
自E=O(V)在二部图中，我们总共得到 O(V^2*log(V))