[POJ 3553] Task schedule【拓扑序+贪心】

  • 2018-01-05
  • 0
  • 0

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 ≤ ij ≤ 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

Northeastern Europe 2003, Western Subregion

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;
}

评论

还没有任何评论,你来说两句吧



新博客地址:
darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io


常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
Please refresh the page if the code cannot be displayed normally.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai