有人可以帮我解决这个问题吗？该解决方案显然是使用网络流，但我对网络流不是很熟悉。网络流如何帮助您解决这个问题？
螃蟹是一个无向图，它有两种顶点：1 个头和 K 个脚，以及将头连接到每条腿的恰好 K 个边。（1 <= K <= T，其中 T 是给定的）
给定一个无向图，您必须在其中找到一些顶点不相交的子图，其中每个子图都是螃蟹。目标是选择这些螃蟹，使它们覆盖的顶点总数最大化。
注意：如果两个图没有任何共同的顶点，则它们是顶点不相交的。
前任 。输入
8 2 7
1 4
2 4
3 4
5 4
5 8
5 7
5 6
想一想如何将 Network Flow 应用到这个问题上。应该是从螃蟹的头到脚的流动。到达头部的流量应该有一个相当于英尺数的值，并且从螃蟹头到脚的每个边缘应该有一个容量。
我们怎样才能做到这一点？自己做这件事肯定很难，但我希望在多次看到这个例子后你能掌握这个窍门。
我们必须创建一个复制原始顶点的新图。一组可以让每个顶点都有机会成为头部，而另一组可以充当脚。记住这一点，精确的算法可以写成如下：-
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.
下图可以很好地了解图形的形成方式。 新图形成
第 3 点的解释：- 头显中的每个顶点都应与容量为 min(t, degree) 的源连接，因为如果我们希望该边缘处的最大流量与 T 一样大，不超过因为因为螃蟹不能超过 t 英尺，并且这里的容量值也受 0 所连接的顶点度数的限制。一个头的脚不能超过它的度数。
第4点的解释：-为了确保对是不相交的，以便每个顶点只出现在一个螃蟹中，每只脚都以容量1连接到图中的目标10。
如果需要，我可以发布代码。
这是一个顶点覆盖问题。对于图的顶点覆盖，蟹头是顶点覆盖的顶点，脚是连接到这些头的顶点。应该去除重复的脚，同时注意不要去除一只螃蟹的所有脚:-)
更新：
最小顶点覆盖是 NP 完全的，不好的 :-) 我认为螃蟹覆盖是等价的。至少有最小的螃蟹覆盖，我们可以获得最小的顶点覆盖。因此，如果最小螃蟹不是 NP 完全的，那么最小顶点覆盖也不应该是 NP 完全的。
让我们证明，拥有最小的螃蟹覆盖，我们可以获得最小的顶点覆盖。以标准方式，我们得到带有蟹头的顶点覆盖。假设相反，有一个度数较低的顶点覆盖，覆盖的顶点比蟹头少。对于那个顶点覆盖，我们可以构造具有相同度数的螃蟹覆盖，除了我们不确定是否存在没有脚的螃蟹，因为移除了重复的脚。只有当一个头和脚与其他头共享，而其他头没有任何其他脚时，才会出现这种情况。在这种情况下，我们可以通过移除这两个头并将头放在关键的脚上来构建更小的顶点覆盖。有了这个我们就有一个矛盾，所以没有顶点少的顶点覆盖。所以最小螃蟹覆盖也是最小顶点覆盖。
通过顶点覆盖方法解决上述问题会导致指数 tim 算法，但这可以通过使用 Ford Fulkerson 算法最大化流来解决上述问题可以使用 Ford Fulkerson 解决。
福特富尔克森算法在给定图中找到最大流量
重复以上 4 个步骤，直到不可能有增广路径。
选择一条可能的路径并确定容量最小的边缘。记录这个数字 从该路径上的每个数字中减去这个数字。这是路径上每条弧线的新容量。选择另一条路线并重复步骤 1 再次记录最小容量。重复直到用尽所有可能的路径。添加所有路线中最小的容量。这是网络的最小承载能力
参考
http://anandtechblog.blogspot.in/search/label/Ford%20Fulkerson%20algorithm
