e-olymp 45. Топливо

Задача

$N$ котелень одинаковой мощности соединены системой трубопроводов из $M$ труб для перекачки топлива. На $09:00$ утра оказалось, что фактические запасы топлива $A_{k}$ тонн $(k=1..N)$ таковы, что в одной из котелень его значительно меньше нормы $B$ тонн, а на остальных — достаточно, либо с избытком.

Суммарные запасы топлива позволяют исправить ситуацию, если перераспределить топливо. В каждый момент времени из $N$ насосов могут работать $0$ или $2$ (в соседних котельных, перекачивающих и принимающих топливо), при этом перекачка одной тонны топлива на $1$ км занимает $C$ минут.

Через какое наименьшее время $T$ минут эта работа будет выполнена?

Входные данные

В первой строке заданы 4 числа $N$,$M$, $B$,$C$. Во второй — массив значений $A_{1..N}$. Далее идут $M$ строк — пары номеров котелень и длины труб между ними. Все данные — неотрицательные целые числа, не превышающие $50$.

Выходные данные

Единственное число — искомое время.

Тесты

5   5   4   6
5  4  8  1  6
1  2  3
2  3  5
2  4  2
3  4  6
3  5  4
102
8 10 8 10
8 11 8 0 8 12 8 12
7 8 2
7 6 4
6 2 3
2 1 4
2 3 1
3 1 2
1 5 9
3 5 6
3 4 5
4 5 2
690
11 10 9 5
9 9 9 9 4 9 12 10 10 9 13
3 1 9
1 2 5
2 8 6
2 7 4
1 4 8
4 5 4
4 6 8
1 9 6
9 10 3
10 11 3
520
2 1 3 1
0 6
1 2 10
30
50 50 43 50
44 44 44 45 2 48 49 46 45 48 43 43 43 45 43 48 49 46 45 48 43 43 43 45 43 48 49 46 45 48 43 44 44 45 43 48 49 46 45 48 44 44 44 45 43 48 49 46 45 48
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 1
23 24 1
24 25 1
25 26 1
26 27 1
27 28 1
28 29 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1
37 38 1
38 39 1
39 40 1
40 41 1
41 42 1
42 43 1
43 44 1
44 45 1
45 46 1
46 44 1
46 48 1
48 49 1
49 50 1
50 1 1
8400
3 3 1 2
3 0 1
1 3 1
2 3 2
1 2 4
6

Решение 1

Решение 2

 Объяснение 1

Вряд ли было бы понятно, если бы я начал сейчас здесь подробно объяснять код. Поэтому, пояснение именно кода я оставлю по этой ссылке, а тут попробую объяснить идею.

Идея решения сама по себе, думаю, достаточно проста: по сути, простой перебор всех вариантов и нахождение наиболее подходящего. Точнее, как бы строится дерево от котла, где недостаёт топлива, и идёт вычисление расстояния до котла, где есть свободное топливо (по веткам связанных с ним котлов). Несколько более сложная, пожалуй, её реализация. В данном решении я воспользовался рекурсивной функцией, которая возвращает либо расстояние до ближайшего котла, откуда можно взять топливо (общее расстояние- то есть все промежуточные котлы, через которое перекачивается топливо, учитываются), либо возвращает $-1$, что говорит о том, что таких котлов (в данной ветке) нет.

Объяснение 2

И снова, сомневаюсь, что мне тут стоит описывать идею решения. А идея — это алгоритм Дейкстры, и вряд ли я сейчас сделаю объясню его лучше этих сайтов. Поэтому я лучше просто  оставлю ссылки на них и на википедию. Отмечу только разницу между переменными $n$ и $visit$ в структуре. $visit$- характеризует вершину, буквально, как посещённую или нет. То есть, рассматривались ли вершины, ведущие из неё. В то время как, $n$— переменная, означающая, принимали ли мы эту вершину во внимание до этого (могли рассматривать путь к данной вершине, но ещё не проверили от неё идущие). Последнюю включил в код просто чтобы не приравнивать $len$ какому-то конкретному числу (по алгоритму, условно, должно быть равно бесконечности). Вектор $dis$-вектор дистанций от данной, к связанной с ней вершинам.

e-olymp 

ideone(1)

ideone(2)

10 thoughts on “e-olymp 45. Топливо

  1. Комментаторам:
    Возможно, станет чуть-чуть понятнее, что откуда взялось, если взглянуть на этот код. Это мой черновик к данной задаче. Он не проходит все тесты, но зато там есть некоторые пометки, которые я, вполне возможно, сам же и пропустил. Так что, если хотите подсказать что-то— вряд ли, конечно, но может быть это поможет.

      • Спасибо за напоминание. Но, как я уже писал выше, то— черновик и оставлен он здесь сугубо из-за комментариев в нём. Код-решение можно случайным образом обнаружить, если прокрутить страницу чуточку выше, до ссылки «ideone»

  2. Уточнение: Тест, который не проходился с циклом «for» — пятый. Есть определённая доля вероятности, что там есть некоторая ошибка. В частности, дано не M строк, а M+1

  3. Кирилл, обрати внимание на раздел в котором ты объясняешь идею решения задачи, ты дважды подряд используется слово «достаточно».

  4. Для данной задачи достаточно алгоритма Дейкстры. Его сложность $O\left(m\cdot\log n\right)$, а у Вас, как я могу догадываться, что-то близкое к экспоненте. Но главное, что сложность его объяснения и понятность кода являются безусловно выигрышными в сравнении с Вашим текущим решением.

    • Да, тогда задачу можно будет зачесть на графы.
      Только лучше не убирать этот код и пояснение.
      Как на фотографиях «до и после»?
      Будет виден прогресс алгоритмической мысли 🙂

      • Удалил 88 пустых строк по тексту. Думал дойдет до 100 и… Не дошло.
      • Алгоритмическая мысль, видимо, несколько продвинулась 🙂 По поводу 88 строчек— судя по всему, так из word копируются таблицы. Постараюсь учитывать в дальнейшем

    • Да, спасибо, учёл, попробовал сделать. Только не уверен, что за логарифмическую сложность вышло, хотя, если не ошибаюсь, похоже на то

Добавить комментарий