Как конвертировать SPOJ Quest4 в минимальную крышку вершин

Question

Ниже приведена проблема с максимальным двупартийным соответствием: http://www.spoj.com/problems/QUEST4/ Через форумы я узнал, что проблема может быть преобразована в проблему с минимальной вершиной, которая, в свою очередь, может быть решена с помощью Maximum Двустороннее соответствие. Однако я не понимаю, как проблема была преобразована в минимальную крышку вершин. Пожалуйста, помогите мне понять это.

Answer 1

Пусть C, R - множество всех строк и всех столбцов. Теперь пусть G - двудольный граф, имеющий ребра между C и R, где имеется ребро (i, j) от C до R, если в i-й строке и j-м столбце есть отверстие.

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

В нашем графе проблем каждый край представляет собой отверстие. Вершины представляют строки или столбцы. минимизировать объективно-блоки, покрывая все отверстия
, что эквивалентно -
минимизировать вершины, покрывая все ребра.