Изменения

== Сведение к задаче о потоке минимальной стоимости ==

Построим двудольный граф <tex>G</tex> следующим образом:

* Имеется исток <tex>S</tex> и сток <tex>T</tex>.

Найдём в полученном графе <tex>G</tex> максимальный [[Поток минимальной стоимости|поток минимальной стоимости]]. <br />

Понятно, что величина потока будет равна <tex>N</tex>. Заметим, что для каждой вершины <tex>i</tex> из первой доли найдётся только одна вершина <tex>j</tex> из второй доли, такая, что поток <tex>f(i, j) = 1</tex>. Поскольку найденный поток имеет минимальную стоимость, то сумма стоимостей выбранных рёбер будет наименьшей из возможных. Поэтому это взаимно однозначное соответствие между вершинами первой доли и вершинами второй доли является решением задачи.

== Асимптотика ==

Асимптотика этого решения равна асимптотике алгоритма, выбранного для поиска потока.