在更大的图中最大二分匹配的有效技巧

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的有向边,从源到A中的元素,从B中的元素到目标.

将来自A中每个元素x的容量为1的有向边添加到x的素因式分解中的每个不同的素数.

将每个素数p的容量为1的有向边添加到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个条目都是偶数)那么也许你的最大流算法有可能达到时间限制.