Как я могу получить элементы антицепи в SPOJ-DIVREL?

Question

Проблема: http://www.spoj.com/problems/DIVREL

В вопросе нам просто нужно найти максимальное количество элементов, которые не кратны (делится на форму b) из заданного набора элементов. Если мы просто сделаем ребро от элемента до его кратного и построим граф, это будет DAG.

Теперь вопрос просто меняется, чтобы найти минимальное число цепочек, которые содержат все вершины, равные количеству антицепей, используя теорему Дилворта, поскольку это частично упорядоченное множество.

Минимальные цепочки могут быть найдены с помощью двустороннего сопоставления (Как: Это минимальное покрытие пути), но теперь я не могу найти сами антицепочечные элементы?

Answer 1

Для вычисления антицепи вы можете:

1. Вычислить максимальное двустороннее сопоставление (например, с алгоритмом максимального потока) на новом двудольном графе D, который имеет ребро от LHS a до RHS b, если и только если a делит b.
2. Используйте сопоставление для вычисления минимального покрытия вершин (например, с помощью алгоритма, описанного в доказательстве теоремы Кенига).
3. Антицепь задается всеми вершинами, не входящими в покрытие вершин.

Между двумя такими элементами не может быть ребра, так как иначе мы бы обнаружили ребро, которое не покрыто покрытием вершины, что привело бы к противоречию.

Алгоритм нахождения минимального покрытия вершин (по ссылке выше):

1. Пусть S0 состоит из всех вершин, не имеющих отношения к M.
2. Для целого числа j ≥ 0 пусть S(2j+1) будет множеством всех вершин v, таких, что v смежно через некоторое ребро в E \ M с вершиной в S(2j) и v не было включено ни в какие ранее определено множество Sk, где k < 2j+1. Если такой вершины нет, но остаются вершины, не включенные ни в один ранее определенный набор Sk, произвольно выберите одну из них, и пусть S(2j+1) состоит из этой единственной вершины.
3. Для целого числа j ≥ 1 пусть S(2j) будет множеством всех вершин u, таких что u смежно через некоторое ребро в M с вершиной в S(2j−1). Обратите внимание, что для каждого v в S (2j − 1) существует вершина u, которой он соответствует, поскольку в противном случае v было бы в S0. Поэтому M устанавливает взаимно-однозначное соответствие между вершинами из S (2j − 1) и вершинами из S(2j).

Объединение нечетных индексированных подмножеств - это покрытие вершин.