При условии полного двудольного графа G = (V1, V2; E), | V1 | = | V2 | = n и неотрицательной стоимости для каждого ребра, задача согласования двудольных минимальных затрат находит разбиение G на n пар вершин, соединенных ребром, так что общая сумма затрат ребер сведена к минимуму.
Эту проблему можно решить с помощью алгоритма min cost flow , добавив вершины источника и приемника подключен к каждой группе с весом 0 и емкостью 1.
Но что, если вместо этого мы получим в качестве входных данных число m
Сначала я подумал, что мы можем просто добавить еще одну вершину в начале, которая связана с исходным источником с весом 0 и емкостью m, и назвать его новым источником, таким образом, максимальный поток будет равен m, и он должен выберите только m пар.
Однако, когда я запускал этот алгоритм, используя функцию минимального расхода наддува, много раз возникали две большие проблемы:
1) Поток в n edge не всегда был целым числом (т. е. вместо 0 или 1 поток был, например, 0,5).
2) Было много возможных (нецелых) решений, поэтому даже для одного и того же ввода с разным порядком алгоритм выдал разные результаты.
В тот момент, когда я установил m равным n, обе эти проблемы были решены.
Поэтому мой вопрос: есть ли способ решить эту проблему, и если нет, то Есть еще один алгоритм, который может решить минимальное стоимостное сопоставление с проблемой выбросов?