ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC, Восточный подрегион, Екатеринбург, октябрь 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

F. Перекачка нефти

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Новый русский Колян хочет, чтобы его главным источником дохода стала доставка нефти зарубежным партнёрам. Его компания владеет несколькими перекачивающими станциями с сетью нефтепроводов, соединяющих их. Прежде всего, Колян хочет увеличить количество перекачиваемой нефти на 1 миллион баррелей в день. Помогите Коляну достигнуть этой цели, потратив минимальное количество денег.

Исходные данные

Первая строка содержит целое число N — количество перекачивающих станций, между которыми есть нефтепроводы (1 ≤ N ≤ 10 000). Станции занумерованы от 1 до N. Следующие N строк описывают станции.
i-я строка содержит четвёрку целых чисел a b c d (1 ≤ aN; 0 ≤ cb ≤ 10 000; 0 ≤ d ≤ 106), где
a — номер станции, к которой существует нефтепровод от станции i,
b — пропускная способность нефтепровода от i до a в миллионах баррелей в день,
c — текущий поток нефти от i до a в миллионах баррелей в день,
d — количество денег (в рублях), необходимое для увеличения пропускной способноти нефтепровода от i до a на 1 миллион баррелей в день. Может быть не более одного нефтепровода от станции i до станции a, и никакой нефтепровод не соединяет станцию с ней самой.
Четвёрки в одной строке разделяются запятыми, после последней четвёрки стоит точка. Если нефть с i-й станции не перекачивается никуда, то соответствующая строка содержит только один символ ".". Гарантируется, что во входных данных содержится не более 100 000 четвёрок, описывающих нефтепроводы.
Нефть перекачивается зарубежным партнёрам только со станции с номером N. Поток нефти через границу равен потоку, входящему в эту станцию. С этой станции нефть не передаётся другим станциям в описанной системе нефтепроводов. Перекачивающие станции с номерами менее N являются транзитными. Известно, что для каждой транзитной станции входящий поток нефти не больше выходящего потока. Если входящий поток меньше, чем выходящий, то поблизости есть нефтяная скважина, добыча нефти в которой может быть легко увеличена на 1 миллион баррелей в день.

Результат

В первой строке выведите минимальную стоимость K такого изменения сети нефтепроводов, что перекачивание нефти зарубежным партнёрам увеличится на 1 миллион баррелей в день. После этого выведите N строк, описывающих поток нефти в трубопроводах после переделки трубопроводов в следующем формате: i-я строка должна содержать список пар a b, разделённых запятыми; a — номер станции, к которой нефть перекачивается со станции i, а b — количество перекачиваемой нефти в миллионах баррелей в день. Каждая из этих строк должна заканчиваться точкой.
Если невозможно достигнуть цели Коляна, выведите единственное слово "Impossible".

Пример

исходные данныерезультат
4
2 1 1 1, 3 1 1 3.
3 1 0 2, 4 1 1 2.
4 1 1 1.
.
2
2 2, 3 1.
3 1, 4 1.
4 2.
.
Автор задачи: Магаз Асанов, Евгений Крохалев
Источник задачи: Quarter-Final of XXXI ACM ICPC - Yekaterinburg - 2006
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1505. Перекачка нефти