2

我不知道如何写这个问题的标题。现有标题可能不准确。

这是问题所在：

我有m组（数组），比如 4 个组。每个组包含一些数字。我们希望每组给出一个数字，并且总共产生的 4 个数字（每个来自一组）是不同的。

现在给定这 4 组，我如何确保它们符合我们的愿望？

例如，

答：0、2、3

乙：0、2

C: 2, 3

D: 1

以上4组可以满足我们的愿望。D给1，C给3，B给2，A给0。

但如果

A2

乙：2

C: 2, 3

D: 1

不好。我们不能让每个组给出一个不同的数字。

我的想法是最愚蠢的方法，我只是对所有组中的所有元素进行回溯，以获取元素的每种组合，并查看来自一个组合的那些元素是否不同。

有人有更好的主意吗？

4

3 回答 3

5

您可以将此建模为网络流问题，然后在该问题域（其中许多是多项式时间）中使用快速算法，例如Edmunds-Karp或push-relabel。

创建源节点和汇节点。然后为每个“组”和每个不同的元素创建节点。将每个组节点连接到源，将每个元素节点连接到接收器。如果组作为元素，最后将组节点与元素节点连接起来。所有流量都应为 1。

最好用一个例子来说明这一点。我将使用您给出的第一个示例：

A: 0, 2, 3
B: 0, 2
C: 2, 3
D: 1

会变成如下流网络：

   A   0
  /     \
 /       \
S--B   1--T
 \       /|
  \     / |
   C   2 /
        /
       3

我无法绘制中间流。但是想象一下，A 流向 0、2、3，B 流向 0、2，C 流向 2、3，D 流向 1。所有流向都是单位容量。

所以首先在这个图中找到最大流量。组和元素之间的流将为您提供所需的二分匹配。

如果没有可能的匹配，则最大流量将小于组数。

于 2012-06-13T14:45:17.137 回答
2

你想要的被称为http://en.wikipedia.org/wiki/Bipartite_graph并且你有一个适用于它的http://en.wikipedia.org/wiki/Maximum_flow_problem#Maximum_cardinality_bipartite_matching。您可以在以下名称下找到算法：Maximum cardinality bipartite matching or maximum flow on a bipartite graph。这是很好的解释http://en.wikipedia.org/wiki/Maximum_matching和http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow , http://community.topcoder.com/tc ?module=Static&d1=tutorials&d2=maxFlow2 希望有所帮助。

于 2012-06-13T14:44:53.927 回答
0

  • 一种想法是寻找所有组独有的元素，并将它们用于它们所属的组；这会将列表缩小到仅具有共同元素的组。

  • 另一个想法是从元素最少的组开始（理想情况下是一个），将它们设置为其中一个值并迭代增加大小（您可以在删除已使用的元素后考虑大小）。

于 2012-06-13T14:49:18.483 回答