POJ 3553 Task schedule【拓扑排序 + 优先队列 / 贪心】-白红宇

POJ 3553 Task schedule【拓扑排序 + 优先队列 / 贪心】

阅读量：7045 次

发布时间：2019-06-28

本文共 2652 字，大约阅读时间需要 8 分钟。

Task schedule

Time Limit: 2000MS Memory Limit: 65536K

Total Submissions: 515 Accepted: 309 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

4 1

4 0

1 2

Sample Output

Source

Northeastern Europe 2003, Western Subregion

【代码】：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,n,x) for(int i=(x); i<(n); i++)#define in freopen("in.in","r",stdin)#define out freopen("out.out","w",stdout)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                      
                        P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int maxm = 1e6 + 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = {0,0,1,-1,1,-1,1,-1};const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};using namespace std;const int maxn = 1e6+5;const int mod = 142857;int n,m,num,u,v;int p[maxn],d[maxn];priority_queue
                        q;vector
                        
                          G[maxn];int inDeg[maxn];void topSort(){ int ok=0; while(!q.empty()) q.pop(); for(int i=1; i<=n; i++) if(!inDeg[i]) q.push(P(d[i],i)); while(!q.empty()) { int now = q.top().second; q.pop(); printf("%d\n",now); for(int i=0;i

转载于:https://www.cnblogs.com/Roni-i/p/9181509.html

你可能感兴趣的文章

Andrew Ng机器学习课程笔记--week1（机器学习介绍及线性回归）