14. Доим коров

Задача

Определите минимальное время, необходимое, чтобы подоить всех коров при наличии ограничений на порядок доения.

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

Первая строка содержит числа $n$ и $m$ ($1 \leqslant n \leqslant 10\,000$, $1 \leqslant m \leqslant 50\,000$) — количество коров и ограничений. Далее следуют $n$ строк, в каждой записано время доения $t_i$ ($1 \leqslant t_i \leqslant 100\,000$). Затем указано $m$ пар $a_i$, $b_i$ ($1 \leqslant a_i, b_i \leqslant n$, $a_i \ne b_i$), означающих, что корову $a_i$ нужно подоить раньше коровы $b_i$.

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

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

Пример

стандартный ввод      стандартный вывод
3 1                    11
10
5
6
3 2

Ограничения

  • Время: 2 секунды
  • Память: 256 мегабайт
Редакционный разбор Зависимости «сначала $a$, потом $b$» образуют ориентированный граф. Минимальное время выполнения всех работ при неограниченном числе исполнителей равно длине критического пути: максимальной сумме длительностей вдоль пути, который уважает все ограничения. Если граф содержит цикл, задача не имеет решения — в условии подразумевается DAG. Строим топологический порядок (например, алгоритмом Кана) и по нему динамически считаем `dp[v]` — минимальное время завершения всех обязательных работ, оканчивающихся в $v$. Формула: `dp[v] = t_v + max(dp[u])` по всем рёбрам `u → v`, а если входящих нет — `dp[v] = t_v`. Ответ — максимум `dp`. Работаем за $O(n + m)$.

Mentioned by