Задача Q. Распространение примеси

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Для того, чтобы оценить величину наносимого ущерба, понадобилось провести ряд исследований, направленных на выявление наиболее вредных объектов промышленности. Однако представители крупных коммерческих предприятий отказались предоставлять точную информацию об объемах сбрасываемых в реку загрязнений. В связи с этим, члены экологического общества поставили перед собой задачу — попытаться восстановить их значения, руководствуясь только лишь данными, полученными из открытых источников.

Карта речной системы представляет собой ориентированный бесконтурный граф (сеть), в узлах которого располагаются очистные сооружения и разнообразные источники загрязнений. На входе указанной сети располагаются узлы, связанные с крупнейшими заводами. Каждый i-й завод непрерывно за одну единицу времени сбрасывает в реку ровно Xi тонн химических отходов.

Известно, что при прохождении через k-й промежуточный узел концентрация примеси изменяется на аддитивную константу Fk. Процент примеси, пропускаемый через ребро, направленное из узла с номером k в узел с номером l, определяется коэффициентом Wk l.

На выходе располагаются системы сбора воды с установленными на них датчиками, которые регистрируют количество примеси Yj, проходящее через них за одну единицу времени.

По имеющимся данным требуется определить концентрацию примеси, выбрасываемую каждым отдельным заводом.

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

Во входном файле "input.txt" хранится карта речной сети, записанная в следующем виде.

Вначале идет пара натуральных значений n и m — число вершин и ребер в таком графе. За ними следует набор из m ребер, каждое из которых задается тремя значениями: k и l — номера вершин, которые оно соединяет; Wk l — весовой коэффициент. При этом полагается, что нумерация вершин начинается с нуля.

На входе такой сети располагаются вершины, связанные с основными заводами. В отличие от остальных вершин, они не имеют входящих ребер. Вершины, имеющие как входные так и выходные ребра, связаны с промежуточными узлами, а вершины, не имеющие выходных ребер — с конечными.

Далее следует список, в котором каждому промежуточному узлу с номером k ставится в соответствие вещественная константа Fk, а каждому конечному узлу с номером j — значение Yj.

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

Если задача имеет единственное решение, в выходной файл "output.txt" выводится строка 'SOLUTION:', за которой следует список из номеров входных узлов i и соответствующих им значений Xi, указанных с точностью до 5-го знака после запятой.

В противном случае, выходной файл должен содержать строку 'INFINITY!'.

Ограничения

Гарантируется, что точное решение всегда существует и удовлетворяет следующим соотношениям: 0 ≤ Xi ≤ 10.

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

Число ребер, исходящих из одной вершины, не превосходит 10, а их суммарный вес равен 1.

0 ≤ Fk ≤ 10, 2 ≤ n ≤ 1000, 0 < m.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10 9
0 3 1.00000
1 6 0.75000
1 4 0.25000
4 6 1.00000
6 3 0.50000
6 7 0.50000
2 5 1.00000
5 8 0.50000
5 9 0.50000

4 2.50480
5 1.39000
6 0.75630

3 5.30580
7 3.41550
8 1.91030
9 1.91030
SOLUTION:
0 1.89030
1 3.56990
2 2.43060
2
8 7
0 3 0.75000
0 4 0.25000
3 5 0.50000
3 6 0.50000
4 7 1.00000
1 4 1.00000
2 4 1.00000

3 1.36070
4 2.04590

5 2.71740
6 2.71740
7 7.41445
INFINITY!

0.138s 0.023s 15