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

Чтобы вычислить антицепь, вы можете:

1. Вычислить максимальное двудольное соответствие (например, с помощью алгоритма максимального потока) для новый двудольный граф D, который имеет ребро из левой части a в правую часть 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).

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