Весенняя олимпиада школьников 2003 года.
Задача первого тура
Даже самый хороший человек на 90
процентов состоит из воды
Братья Марио
Водопровод
Водопроводная сеть состоит из труб разной пропускной способности.
Вода по любой трубе может течь в любую сторону. Все места соединения труб
учтены и пронумерованы целыми числами от 0до 10000. Особо выделены места с
номерами 0 и 1. На самом деле, 0 это не соединение труб, а место, в котором
подаётся вода в трубы, а 1 -- место, откуда вода вытекает.
У каждой трубы известна пропускная способность -- максимальное количество
воды протекающей по трубе, за единицу времени, при котором она ещё не лопнет.
ЗАДАЧА
Цель: добиться того чтобы в узел 1 текло как можно больше воды.
Определить каково необходимое количество воды протекающей по каждой трубе
(напор) для достижения цели.
Превышать пропускную способность трубы нельзя, а то труба может лопнуть.
ТЕХНИЧЕСКОЕ ЗАДАНИЕ
Поток воды в трубе должен быть целым числом.
В файле pipes.txt находится описание соединения. Ответ нужно записать в
файл water.txt в указанном формате.
Задача оценивается соревновательно. Максимальное количество баллов получают
решения с максимальным количеством воды поступающей в узел (приток) 0.
Из решений с одинаковым притоком считается лучшим то, где будет присутствовать
больше труб с нулевым напором. Максимальное количество баллов за
задачу: 100.
Командный вариант
Эту задачу можно решать не только одному.
Вы можете собрать команду до 4 человек.
Команда более чем из одного человека получит поощрительные очки:
2 человека -- 10 баллов,
3 человека -- 15 баллов,4 человека -- 20 баллов.
Баллы набранные командой не делятся, а каждый участник команды получает все
баллы заработанные командой.
Автор задачи: В.В.Пупышев
Последний день присылать решения задачи -- 20 марта 2003 года.
Последний день задавать вопросы по условию задачи -- 14 марта 2003 года.
Вопросы и решения присылайте по адресу: olymp_mark@uni.udm.ru