Pro.ID22705 TitleTask schedule Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22705 AC0 Submit0 Ratio- 时间&空间限制描述There are n preemptive jobs to be processed on a single machine. Each job j has a processing time pj and deadline dj. Preemptive constrains are specified by oriented graph without cycles. Arc(i, j) in this graph means that job i has to be processed before job j. A solution is specified by a sequence of the jobs. For any solution the completion time Cj is easily determined. The objective is to find the optimal solution in order to minimize max { Cj - dj , 0 }. 输入The first line contains a single integer n, 1 ≤ n ≤ 50000. Each of the next n lines contains two integers pj and dj, 0 ≤ pj ≤ 1000, 0 ≤ dj ≤ 1000000, separated by one or more spaces. Line n+2 contains an integer m (number of arcs), 0 ≤ m ≤ 10×n. Each of the next m lines contains two integers i and j, 1 ≤ i, j ≤ n. 输出Description There are n preemptive jobs to be processed on a single machine. Each job j has a processing time pj and deadline dj. Preemptive constrains are specified by oriented graph without cycles. Arc(i, j) in this graph means that job i has to be processed before job j. A solution is specified by a sequence of the jobs. For any solution the completion time Cj is easily determined. The objective is to find the optimal solution in order to minimize max { Cj - dj , 0 }. Input The first line contains a single integer n, 1 ≤ n ≤ 50000. Each of the next n lines contains two integers pj and dj, 0 ≤ pj ≤ 1000, 0 ≤ dj ≤ 1000000, separated by one or more spaces. Line n+2 contains an integer m (number of arcs), 0 ≤ m ≤ 10×n. Each of the next m lines contains two integers i and j, 1 ≤ i, j ≤ n. Output Output n lines contains integer i (number of job in the optimal sequence). Sample Input 2 Sample Output 1 Source 样例输入2 样例输出1 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-5 18:48 , Processed in 0.037124 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
