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 条从它出去的边来覆盖 As。

另一个例子:

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。不能少于这个数量。

我已经实现了基本的福特富尔克森算法，我知道这也是网络流，但不知道如何与之关联。

如果有人可以提供有关图表的一些提示，那就太好了。

谢谢

Answer 1

找到一个最佳解决方案 - 所有 B 最多有一个出边(如果存在)很简单:

• 向图中添加源和接收器。源会有一个输出 容量为 1 的边到 B 列表中的所有顶点。
• 全部 (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))