algorithm - 数组的二分匹配

Question

我有数组 A 和 B。我必须找到数组 B 的最大匹配，这样 B[i] 的每个索引都可以与 A[j] 的任何索引匹配当且仅当 A[j ]!=B[i] 和 A[j] 之前没有匹配。例如:

A = {1 2 3 4}
B = {2 2 3 4}
Maximum Matching is 4 A[0]=B[3] , A[1]=B[2] , A[2]=B[1], A[3]=B[0]

A = {1 1 2}
B  = {1 1 2}
Maximum Matching 2 A[0]=B[2] , B[1]=No Matching , A[2]=B[0]

我知道这是最大二分问题，但问题是 A=B<=10^3 和 A[i],B[i]<10^6 的长度。这将使我的二分解决方案超时。有没有更好的解决方案？

代码:

public static boolean is_match(int curr) {
    for(int i = 0; i < A.length; i++) {

        if(A[i] != curr && !V[i]) {

            V[i] = true;
            if(P[i] < 0 || is_match(P[i])) {
                P[i] = curr;
                return true;
            }
        }
    }
    return false;
}

我为每个 B 调用这个函数:

for(int i:B){
    V = new boolean[n]
    if(is_match(i)) match++;
}

如何改进我的解决方案？

Answer 1

这个问题可以可视化为最大流问题。

因此，由于条件是 A[j]!=B[i] 且 A[j] 之前未匹配，所以知道索引 i 是否来自 A 匹配到 B 中的 j 或 k 且 B[j] == B[k] 并不重要。

因此，不是将图表示为 2*n 节点的二分图，而是每个节点表示数组 A 和 B 中的一个索引，我们可以将问题表示为具有一个源节点的流程图，一个汇节点和代表A和B唯一值的节点列表，节点a(代表A中的a值)到源节点的容量是A 中具有值 a 的索引数量。同理，节点b映射到下沉节点的容量等于B中索引值为b的个数。从A到B的有效节点之间的容量是无穷大。

例如，数组 A = {1, 1, 2, 2} 和 B = {1, 2, 2, 3, 3, 3, 3}

因此，我们创建了一个带有源节点和汇节点的流图。

• 此外，对于数组 A，我们创建了两个额外的节点，一个用于值 1，一个用于值 2。源节点将连接到这两个节点。

• 对于节点 B，我们创建三个节点，一个值 1，一个值 2，一个值 3。

• 现在，源节点将只连接到数组 A 中的节点，容量等于:节点 2 代表值 1(因为数组 A 中有两个 1)，节点 2 代表值 2(有两个2 在数组 A 中)。

• Sink 节点将只连接到数组 B 中的节点，容量为:1 for node 代表值1(数组B中只有一个1)；节点的2表示值2(数组B中有两个2)，节点的4表示值3(数组B中有四个3)。

• 从数组 A 到 B 的有效节点之间的连接将具有无穷大的容量。

现在剩下的工作是运行典型的最大流算法。