Topic: The simple task or...?
The maximum operating time on one test: 2 seconds the Maximum memory size: 256 MB Are set n various tasks. And, to do some jobs it is possible only after others are fulfilled. For each task it is defined, how many minutes are necessary, that it to fulfill. As to carry out in time all tasks it does not turn out, therefore the decision to make all tasks except one - because of one outstanding task of problems does not arise. Now it is necessary to select, what task not to fulfill, that other tasks to fulfill as soon as possible. A format of an input file the First line of an input file contains integer numbers n and m - an amount of tasks and an amount of dependences between tasks (1 <= n <= 100, 0 <= m <= 1000). The second line contains n integer numbers: t 1, t 2..., t n. The number t i means an amount of the minutes necessary for performance of i tasks (1 <= t i <= 1000). Further goes m lines, each of which contains two integer numbers. Numbers an and b mean that an it is necessary to fulfill the task earlier, than the task b. It is guaranteed that all tasks can be fulfilled. An output file format to Deduce one number - the minimum quantity of the minutes necessary for performance of all tasks except one. input.txt output.txt 5 5 11 1 2 3 4 5 1 2 5 3 1 3 3 4 2 4 in the given example it is possible not to carry out the fourth task. All remaining tasks will be fulfilled for 11 minutes. From the job and an example follows: 1) the graph where each peak has the weight is given; 2) it is necessary to discard 1 peak so that: all remaining peaks remained accessible in the column; on the remained peaks - minimum. My decision: 1) to find Suma - scales for all peaks; 2) to create the list of all peaks-leaves; 3) under the list of peaks-leaves: if (minSuma> Suma - (peak-leaf weight)) then minSuma = Suma - (peak-leaf weight) the Key moment of my decision: search of peaks-leaves which as it is represented to me, it is possible to fulfill in time About (1). A question: 1) whether provides a condition not only the acyclic graph, but also wood from such graphs? 2) whether really such algorithm all task, and not just the resulted example dares: whether it is correct, what I focus attention only on peaks-leaves?