Тема: timus 1505
http://acm.timus.ru/problem.aspx?space=1&num=1505
Непонятные траблы с этой задачей у меня.
Идея такая:
1) найдем все вершины, которые являются источниками.
2) создадим граф, ориентированные ребра которого - каналы, вершины - станции перекачки.
3) если для канала поток меньше пропускной способности, то вес ребра = 0, иначе вес ребра равен стоимости увеличения пропускной способности на 1.
4) если в канале поток не равен нулю, то существует обратное ребро с весом = 0.
Далее найдем кратчайший путь от источников к стоку. Ну это алгоритм Дейкстры на основе очереди с приоритетом.
Затем внесем изменения в граф для ребер, составляющих кратчайший путь. Выведем ответ.
Получаю WA 31. Может косяк в идее?
Спасибо заранее.