Максимальное время работы на одном тесте: 2 секунды
Максимальный объем памяти: 256 Мб
Задано n различных задач. Причем, делать некоторые задания можно только после того, как выполнены другие.
Для каждой задачи определено, сколько минут нужно, чтобы её выполнить. Поскольку выполнить вовремя все задачи не получится, поэтому приянто решение сделать все задачи кроме одной — из-за одной невыполненной задачи проблем не возникнет.
Теперь следует выбрать, какую задачу не выполнять, чтобы другие задачи выполнить как можно быстрее.
Формат входного файла
Первая строка входного файла содержит целые числа n и m — количество задач и количество зависимостей между задачами (1 ≤ n ≤ 100, 0 ≤ m ≤ 1000). Вторая строка содержит n целых чисел: t
1, t
2,. . . , t
n. Число t
i означает количество минут, необходимых для выполнения i-той задачи (1 ≤ t
i ≤ 1000). Далее идет m строк, каждая из которых содержит два целых числа. Числа a и b означают, что задачу a следует выполнить ранее, чем задачу b. Гарантируется, что все задачи можно выполнить.
Формат выходного файла
Вывести одно число — минимальное количество минут, необходимых для выполнения всех задач кроме одной.
input.txt output.txt
5 5 11
1 2 3 4 5
1 2
5 3
1 3
3 4
2 4
В данном примере можно не выполнять четвертую задачу. Все остальные задачи выполнятся за 11 минут.
Из задания и примера следует:
1) дано граф, где каждая вершина имеет свой вес;
2) нужно отбросить 1 вершину так, чтобы: а) все остальные вершины остались доступными в графе; б) сума по оставшимся вершинам — минимальная.
Мое решение:
1) найти Suma — суму весов для всех вершин;
2) создать список всех вершин-листьев;
3)
по списку вершин-листьев:
if (minSuma > Suma - (вес вершины-листка) )
then minSuma = Suma - (вес вершины-листка)
Ключевой момент моего решения: поиск вершин-листьев, который, как мне представляется, можно выполнить за время О(1).
Вопрос:
1) предусматривает ли условие не только ациклический граф, но и лес из таких графов?
2) действительно ли таким алгоритмом решается вся задача, а не только приведенный пример: правильно ли, что я акцентирую внимание только на вершинах-листьях?
