c++ - 大图中最大二分匹配的有效技巧

Question

问题：给定两个整数数组 A 和 B。现在，在每个步骤中，我们都可以从两个数组中删除任何 2 个非互质整数。我们必须找到可以通过这些步骤删除的最大对数。

界限： A、B 的长度 <=10 ⁵
每个整数 <=10 ⁹
Dinic 算法 - O(V ² E)
Edmonds-karp 算法 - O(VE ² )
Hopcroft–Karp 算法 - O(E sqrt(V))

到目前为止我的方法：这可以建模为具有两个集合 A 和 B 的二分匹配问题，并且可以在相应集合中的每个非互质整数对之间创建边。
但问题是图中可能有 O(V ² ) 条边，大多数二分匹配和最大流算法对于如此大的图来说会非常慢。

我正在寻找一些可以在合理时间内解决问题的特定问题或数学优化。要通过测试用例，我最多需要 O(V log V) 或 O(V sqrt(V)) 算法。

提前致谢。

Answer 1

您可以尝试制作一个带有顶点的图形：

1. 来源
2. A 中的每个元素
3. A 中任意数中的每个素数
4. B 中的每个元素
5. 目的地

将容量为 1 的有向边从源添加到 A 中的元素，从 B 中的元素添加到目标。

将容量为 1 的有向边从 A 中的每个元素 x 添加到 x 的素数分解中的每个不同素数。

将容量为 1 的有向边从每个素数 p 添加到 B 中的每个元素 x，其中 p 除以 x

然后求解从源到目的地的最大流量。

这些数字将包含少量因子（最多为 9，因为 2.3.5.7.11.13.17.19.23.29 大于 10**9），因此中间最多有 1,800,000 条边。

这比您以前可能拥有的 10,000,000,000 条边要少得多（例如，如果 A 和 B 中的所有 100,000 个条目都是偶数），因此您的最大流量算法可能有机会满足时间限制。