algorithm - 螃蟹图，算法，图论，这个网络流程如何？

Question

有人可以帮我解决这个问题吗？该解决方案显然是使用网络流，但我对网络流不是很熟悉。网络流如何帮助您解决这个问题？

螃蟹是一个无向图，它有两种顶点:1 个头和 K 个脚，以及连接头和每条腿的恰好 K 条边。(1 <= K <= T，其中 T 是给定的)

给定一个无向图，你必须在其中找到一些顶点不相交的子图，其中每个子图都是一只螃蟹。目标是以最大化它们覆盖的顶点总数的方式选择这些螃蟹。

注意:如果两个图没有任何公共(public)顶点，则它们是顶点不相交的。

例如。输入

8 2 7
1 4
2 4
3 4
5 4
5 8
5 7
5 6

Answer 1

想想网络流如何应用到这个问题上。应该是螃蟹头上有一股水流到脚上。到达头部的流量应该有一个等于脚数的值，螃蟹从头到脚的每条边的容量应该是 1。

我们怎样才能做到这一点？一个人肯定很难做到这一点，但我希望在多次看到这个例子后，你能掌握这一点。

我们必须创建一个新图，其中原始顶点是重复的。一组可以让每个顶点都有机会成为头部，另一组可以充当脚。牢记这一点，精确的算法可以写成如下:-

1. We create a new graph where original vertices are duplicated (vertex i  becomes 2*i (head set) and 2*i+1  (feet set)    ).

2.For i and j vertices connected in original graph make sure that 2*i and 2*j+1 plus 2*j and 2*i+1 gets connected in new graph with capacity 1.

3.source vertex (S) is connected to each 2*i vertex(head set) with capacity min(T, degree).
4. Each 2*i+1(feet set) vertex is connected to target vertex (T) with capacity 1
5. Maxflow is the answer.

下图可以很好地说明图形的形成方式。 New Graph formation

第 3 点的解释:- 耳机中的每个顶点都应与容量为 min(t, degree) 的源连接，因为如果我们希望该边缘的最大流量与 T 一样大，而不是更多不是因为螃蟹不能超过 t 英尺，这里的容量值也受 0 连接的顶点的度数限制。一个头的脚数不能超过它的度数。

第 4 点的解释:- 为了确保对不相交，以便每个顶点只出现在一只螃蟹中，每只脚都以容量 1 连接到图中的目标 10。

如果需要，我可以发布代码。