G. Нефть

Имя входного файла: oil.in
Имя выходного файла: oil.out
Ограничение по времени: 1 s
Ограничение по памяти: 256 megabytes

Однажды в городе П. решили построить нефтяную сеть. Для этого было построено n транспортных узлов, которые соединялись между собой m нефтепроводами. Стоит помнить, что нефть по трубопроводу течет только в одну сторону. Из-за приближающегося срока сдачи проекта в эксплуатацию подрядная организация начала очень быстро сооружать узлы и трубопроводы. Для каждого нефтепровода известно направление движения и объем протекающей нефти, измеренный в литрах в секунду. Не трудно заметить, что при этом в некоторых узлах может возникнуть избыток/недостаток нефти в том смысле, что втекает/вытекает нефти больше, чем вытекает/втекает. Требуется определить в каких вершинах необходимо докачивать нефть, а в каких сливать неиспользуемый избыток для того, чтобы соблюдался баланс (количество втекающей нефти должно быть равно количеству вытекающей с учето дополнительной откачки/долива).

Формат входного файла

В первой строке содержатся целые числа n и m (1 ≤ n, m ≤ 100000). В следующих m строках находятся описания нефтепроводов: тройка чисел u, v, c, где u – номер узла, из которого вытекает нефть в узел v со скоростью c литров в секунду (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ c ≤ 10000). Узлы нефтесети пронумерованы целыми числами от 1 до n, между двумя узлами может быть более одного нефтепровода.

Формат выходного файла

В выходной файл выведите n чисел – информацию об изменениях в каждом узле: i-ое число равно ci и удовлетворяет одному из следующих условий:

  1. если ci отрицательное, то из узла i необходимо дополнительно слить -ci (л/сек),
  2. если ci положительное, то в узел i необходимо дополнительно закачать ci (л/сек),
  3. если ci равно нулю, то производить изменения с узлом i не нужно, так как соблюдается баланс объема втекающей и вытекающей нефти.

Пример:

oil.inoil.out
4 4 1 2 3 2 3 4 3 4 4 4 1 2 1 1 0 -2


Источник: Первенство ПетрГУ. Сентябрь 2012.

Обсудить       Отправить решение



Версия для печати