Что прочитать
Олимпиадник готовится по этому каталогу. За каждую решённую задачу он получает очки, но решать задачу можно, только прочитав все статьи, к которым она относится, а читать статью — только прочитав её предпосылки. Чтение отнимает время, и минута чтения стоит очко. Что прочитать и что решить, чтобы разность «очки минус минуты» была наибольшей?
В общем виде: есть n дел, у каждого — ценность v, положительная (задача) или отрицательная (статья, на которую уходит время). Некоторые дела требуют других: взяться за a можно, только взявшись и за b. Требования могут образовывать циклы — тогда такие дела берут вместе или не берут вовсе. Выберите набор дел, который вместе с каждым делом содержит всё, что оно требует, с наибольшей суммой ценностей. Пустой набор разрешён.
Тесты 3 и 4 — сам каталог на 17 октября 2026 года: 155 статей с их временем чтения и предпосылками и 286 задач, за каждую единицу сложности задачи дают 10 очков в третьем тесте и 15 — в четвёртом.
Вход
В первой строке n и m (1 ≤ n ≤ 2000, 0 ≤ m ≤ 20 000). Во второй — n ценностей v1, …, vn (|vi| ≤ 10⁹). Дальше m строк a b (1 ≤ a, b ≤ n, a ≠ b): дело a требует дела b.
Выход
Наибольшую сумму ценностей допустимого набора.
Примеры
Пример 1
3 2 6 6 -10 1 3 2 3
2
Пример 2
4 4 -4 -5 7 3 1 2 2 1 3 1 4 3
1
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Проверьте первый пример: каждая задача в одиночку не окупает статью, а вдвоём окупают. Можно ли решать «задачу за задачей»?
2Подсказка 2
Представьте выбор как разрез: исток — «берём», сток — «не берём». Какие рёбра должны попасть в разрез, если задачу не взяли? Если статью взяли? А что сделать с требованием «a без b нельзя», чтобы разрез с таким нарушением стал недопустимо дорогим?
3Идея
Это задача о замыкании наибольшего веса, и она сводится к минимальному разрезу. Из истока в каждое дело с v > 0 ведём ребро ценой v, из каждого дела с v < 0 в сток — ценой −v, а для каждого требования «a требует b» — ребро a → b бесконечной цены. Ответ — сумма положительных ценностей минус величина наибольшего потока.
4Разбор
Пусть S — сторона разреза с истоком, и набор дел — вершины S. Разрез конечен тогда и только тогда, когда ни одно бесконечное ребро a → b не ведёт из S наружу, то есть набор вместе с каждым делом содержит всё, что оно требует. Цена такого разреза складывается из двух частей: рёбра исток → v для невзятых положительных дел (упущенные очки) и рёбра v → сток для взятых отрицательных (потраченные минуты). Значит, цена разреза = (сумма всех положительных) − (сумма ценностей набора). Минимальный разрез даёт наибольшую сумму набора, а его цену находит максимальный поток — здесь алгоритм Диница.
Циклы в требованиях ничему не мешают: бесконечные рёбра в обе стороны просто не дают разрезать цикл.
На каталоге при 10 очках за единицу сложности ответ — 3554. Жадный выбор «задача за задачей», который берёт задачу, только если она одна окупает всё недостающее, получает 82: у статей каталога много общих предпосылок, и окупаются они только вместе.
4+Решение
5Сложность
Вершин n + 2, рёбер не больше n + m. Алгоритм Диница — O(V² E) в худшем случае, на таких графах — много быстрее. Длинные цепочки требований — плохой случай для Диница: каждая фаза удлиняет путь на одно ребро, поэтому в тестах цепочки не длиннее 600.
6Типичные ошибки
- Задачи по одной. Решать, брать ли задачу, глядя только на неё, — это
wrong.py. Он не видит, что две задачи вместе окупают общую статью, которую ни одна не окупает отдельно. - Конечная «бесконечность». Если бесконечное ребро дешевле суммы всех ценностей, разрез может предпочесть его, и требование нарушится. Ценности доходят до 10⁹, их сумма — до 2·10¹²: «бесконечность» нужна больше.
- 32-битная сумма. В седьмом тесте ответ не помещается в 32 бита.