Здравствуйте, уважаемые форумчане!
Я получил следующую задачу на графах и не знаю существует ли метод ее решения:
Дан взвешенный ориентированный граф, у которого некоторые вершины окрашены в один из
цветов.
Задача состоит в том, чтобы покрасить остальные вершины этими цветами так, чтобы граф распался на непересекающиеся пути, состоящие из вершин одного цвета так, чтобы сумма весов всех ребер вдоль путей была минимальна.
Подозреваю, что здесь возможно применение решения задачи максимального потока в той или иной модификации.
Заранее спасибо.
