[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;
}
发表评论