проблема назначения с затратами

Question

У меня есть проблема, с которой я застрял, и не могу найти нигде, чтобы начать, поэтому я безнадежно обращаюсь к stackoverflow.

проблема хочет, чтобы мы выяснили, является ли он np-сложным или полиномиальным, если его np-hard доказывает np-полноту, иначе приведем алгоритм.

проблема заключается в следующем:

продукт существует из n модулей. есть две компании, которые могут построить каждый модуль с определенной стоимостью (c_ij, i: номер модуля, j: номер компании). если модули a и b построены разными компаниями, они также имеют дополнительную стоимость (p_ab). Модули a и b не обязательно должны быть последовательными, такие же дополнительные расходы применяются также для a и c. Как и ожидалось, проблема заключается в том, чтобы мы нашли назначение модулей компаниям, чтобы общая стоимость была минимальной.

есть идеи?

Answer 1

Это может быть сведено к проблеме минимального разреза, которая может быть найдена любым алгоритмом максимального потока. Так что за сеть? Модули будут вершинами нашего графа, а также мы добавим 2 новые вершины - источник и сток. Из источника мы добавляем ребро в каждый модуль i с емкостью Ci1. Аналогично из каждого модуля i мы добавляем ребро в сток емкостью Ci2. Также для любых модулей i и j мы добавляем ребро с емкостью pij (граф ориентирован таким образом, будет два ребра (i j) и (j i)). Легко видеть, что значение min cut является решением проблемы (модули в части разреза с источником присваивают второй компании, а остальные модули - первой компании)