Эффективный трюк для максимального двудольного соответствия на большом графике
проблема: Нам дают два массива А & B целых чисел. Теперь на каждом шаге нам разрешается удалять любые 2 не взаимно простых числа каждое из двух массивов. Мы должны найти максимальное количество пар, которые можно удалить с помощью этих шагов.
Границы:
длина А, В <= 105
каждое целое число <= 109
Алгоритм Диника — O (V2E)
Алгоритм Эдмондса-Карпа — O (VE2)
Алгоритм Хопкрофта – Карпа — O (E sqrt (V))
Мой подход до сих пор: Это может быть смоделировано как проблема двустороннего сопоставления с двумя наборами A и B, и ребра могут быть созданы между каждой непростой парой целых чисел из соответствующего набора.
Но проблема в том, что может быть O (V2) ребра в графе и большинство алгоритмов двустороннего сопоставления и максимального потока будут очень медленными для таких больших графов.
Я ищу какую-то конкретную проблему или математическую оптимизацию, которая может решить проблему в разумные сроки. Чтобы пройти тесты, мне нужно не более O (V log V) или O (V sqrt (V)) алгоритм.
Заранее спасибо.
Решение
Вы можете попробовать сделать граф с вершинами для:
- Источник
- Каждый элемент в
- Каждое простое число в любом числе в A
- Каждый элемент в B
- Пункт назначения
Добавьте направленные ребра емкостью 1 от источника к элементам в A и от элементов в B к месту назначения.
Добавьте направленные ребра емкостью 1 от каждого элемента x в A к каждому отдельному простому в простой факторизации x.
Добавьте направленные ребра емкостью 1 от каждого простого числа p к каждому элементу x в B, где p делит x
Затем найдите максимальный поток от источника к месту назначения.
Числа будут иметь небольшое количество факторов (самое большее 9, потому что 2.3.5.7.11.13.17.19.23.29 больше, чем 10 ** 9), поэтому у вас будет не более 1 800 000 ребер в середине.
Это намного меньше, чем 10 000 000 000 ребер, которые вы могли иметь раньше (например, если бы все 100 000 записей в A и B были четными), поэтому, возможно, ваш алгоритм максимального потока имеет шанс соблюсти ограничение по времени.
Другие решения