Задача проблемы с расходами

Question

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

Проблема хочет, чтобы мы выяснили, если это NP-Hard или Polynomial, если его NP-Hard доказывает NP-полнота, а также дать алгоритму.

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

Продукт существует из N модулей. Есть две компании, которые могут построить каждый модуль, с некоторыми затратами (C_IJ, I: номер модуля, J: номер компании). Если модули A и B построены различными компаниями, у них также есть дополнительные расходы, (P_AB). Модули A и B не должны быть последовательными, одинаковые дополнительные затраты применяются для A и C. Как и ожидалось, проблема хочет, чтобы мы нашли назначение модулей для компаний, так что общая стоимость минимальная.

есть идеи ?

Answer 1

Он может быть уменьшен до минимальной режущей задачи, которая может быть найдена любым максимальным алгоритмом потока. Так какая сеть? Модули будут вершины нашего графика, а также добавляем 2 новых вершины источника и раковины. Из источника мы добавляем край на каждый модуль I с емкостью Ci1. Точно так же из каждого модуля я добавляю край, чтобы погрузиться с емкостью Ci2. Также для любых модулей I и J мы добавляем край емкости Pij (ориентированы на график, при этом будут два ребра (IJ) и (Ji)). Легко видеть, что значение Min Cut - это решение проблемы (модули в части среза с источником назначают вторую компанию и модули отдыха в первой компании)