[POJ 3553] Task schedule【拓扑序+贪心】
Problem:
Time Limit: 2000MS | Memory Limit: 65536K | Special Judge |
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
Each of the n lines contains integer i (number of job in the optimal sequence).
Sample Input
2 4 1 4 0 1 1 2
Sample Output
1 2
Source
Solution:
本题拓扑排序的要求很明显,直接套用 Kahn's Algorithm 即可,注意要用邻接表储存。
而暂不考虑拓扑序,我们可以发现这是一道经典的贪心题,每次只需贪截止时间最小的即可。
【贪心证明】
令 d[i] 为第 i 件工作的截止时间, p[i] 为第 i 件工作的耗费时间。若当前已用时间 T,接下来在 i, j 中选一个先加工,且 d[i] < d[j],则
- 先加工 i:max{T + p[i] - d[i], T + p[i] + p[j] - d[j]} …… i)
- 先加工 j:max{T + p[j] - d[j], T + p[j] + p[i] - d[i]} …… ii)
设 S = T + p[i] + p[j],则
- i) 可化为:max{S - p[j] - d[i], S - d[j]} = S + min{p[j] + d[i], d[j]}
- ii) 可化为:max{S - p[i] - d[j], S - d[i]} = S + min{p[i] + d[j], d[i]} = S + d[i]
由于 p[j] + d[i] > d[i],且 d[j] > d[i],S + min{p[j] + d[i], d[j]} > S + d[i],即先加工 i 一定较先加工 j 更优。
【华丽丽的 Q.E.D.】
所以只需要开一个优先队列存放入度为 0 的点,取一个输出一个即可。
Code: O(NlogN+M) [1564K, 313MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<queue> using namespace std; typedef pair<int, int> PII; int n, m; struct Job{ int p, d; } job[50005]; struct Edge{ int np; Edge *nxt; }; struct Graph{ Edge *V[50005], E[500005]; int tope; inline void addedge(int u, int v) {E[++tope].np = v, E[tope].nxt = V[u], V[u] = &E[tope];} } G; int indeg[50005]; priority_queue<PII, vector<PII>, greater<PII> > deg0; int main(){ scanf("%d", &n); for(register int i = 1; i <= n; i++) scanf("%d%d", &job[i].p, &job[i].d); scanf("%d", &m); for(register int i = 1; i <= m; i++){ int u, v; scanf("%d%d", &u, &v); G.addedge(u, v), indeg[v]++; } for(register int i = 1; i <= n; i++) if(!indeg[i]) deg0.push(PII(job[i].d, i)); while(!deg0.empty()){ int u = deg0.top().second; deg0.pop(); printf("%d\n", u); for(register Edge *ne = G.V[u]; ne; ne = ne->nxt) if(!--indeg[ne->np]) deg0.push(PII(job[ne->np].d, ne->np)); } return 0; }
发表评论