Здравствуйте, olimp_20, Вы писали:

_>Задано n различных задач. Причем, делать некоторые задания можно только после того, как выполнены другие.
_>Для каждой задачи определено, сколько минут нужно, чтобы её выполнить. Поскольку выполнить вовремя все задачи не получится, поэтому приянто решение сделать все задачи кроме одной — из-за одной невыполненной задачи проблем не возникнет.
_>Теперь следует выбрать, какую задачу не выполнять, чтобы другие задачи выполнить как можно быстрее.
_>

_>input.txt   output.txt   
_>5 5         11
_>1 2 3 4 5
_>1 2
_>5 3
_>1 3
_>3 4
_>2 4
_>

_>В данном примере можно не выполнять четвертую задачу. Все остальные задачи выполнятся за 11 минут.

Выкинуть можно только те задачи, у которых нет зависимых. То есть те, которые не встречаются в левой колонке. (В примере такая задача только одна, 4).
Среди них нужно найти ту, чьё время максимально (если задачи выполняются строго последовательно) или ту, через которую идёт максимальный поток (если параллельно).

Если построим диаграмму Ганнта

  0 1 2 3 4 5 6 7 8 9 0 1
1 |=|
2 | |===|
3 | |       |===|
4 |     |   |   |.......|
5 |=========|

то ответ для всех-без-одной при распараллеливании равен 7.

Но раз ответ — 11, это соответствует последовательному выполнению.
То есть, заниматься топологической сортировкой нет нужды. Просто находим максимальную из всех не создающих зависимости. Это делается за единственный проход.

Здравствуйте, olimp_20, Вы писали:

_>Задано n различных задач. Причем, делать некоторые задания можно только после того, как выполнены другие.
_>Для каждой задачи определено, сколько минут нужно, чтобы её выполнить. Поскольку выполнить вовремя все задачи не получится, поэтому приянто решение сделать все задачи кроме одной — из-за одной невыполненной задачи проблем не возникнет.
_>Теперь следует выбрать, какую задачу не выполнять, чтобы другие задачи выполнить как можно быстрее.
_>

_>input.txt   output.txt   
_>5 5         11
_>1 2 3 4 5
_>1 2
_>5 3
_>1 3
_>3 4
_>2 4
_>

_>В данном примере можно не выполнять четвертую задачу. Все остальные задачи выполнятся за 11 минут.

Выкинуть можно только те задачи, у которых нет зависимых. То есть те, которые не встречаются в левой колонке. (В примере такая задача только одна, 4).
Среди них нужно найти ту, чьё время максимально (если задачи выполняются строго последовательно) или ту, через которую идёт максимальный поток (если параллельно).

Если построим диаграмму Ганнта

  0 1 2 3 4 5 6 7 8 9 0 1 2
1 |=|
2 | |===|
3 | |       |=====|
4 |     |   |     |.......|
5 |=========|

то ответ для всех-без-одной при распараллеливании равен 8.

Но раз ответ — 11, это соответствует последовательному выполнению.
То есть, заниматься топологической сортировкой нет нужды. Просто находим максимальную из всех не создающих зависимости. Это делается за единственный проход.