poj3553 拓扑序+排序贪心

题意：有多个任务，每个任务有需要花费的时间和最后期限，任务之间也有一些先后关系，必须先完成某个才能开始某个，对于每个任务，如果没有越期，则超时为0，否则超时为结束时间-最后期限，求超时时间最大值最小的任务顺序。

由于完成这些任务的总时间是一样的，所以只要贪心地尽量取结束时间早的先做就行，只不过加上了拓扑序的限制，就将任务按结束时间排大小，拓扑序做就行了。

 #include<stdio.h>

 #include<string.h>

 #include<queue>

 using namespace std;

 const int maxn=5e4+;

 const int maxm=5e5+;

 struct job{

     int p,d,id,num;

     bool operator < (const job a)const{

         return d<a.d;

     }

 }w[maxn];

 int head[maxn],point[maxm],nxt[maxm],size;

 int n;

 void init(){

     memset(w,,sizeof(w));

     memset(head,-,sizeof(head));

     size=;

     for(int i=;i<=n;++i)w[i].num=i;

 }

 void add(int a,int b){

     point[size]=b;

     nxt[size]=head[a];

     head[a]=size++;

     w[b].id++;

 }

 void topo(){

     priority_queue<job>q;

     for(int i=;i<=n;++i)if(!w[i].id)q.push(w[i]);

     while(!q.empty()){

         job u=q.top();

         q.pop();

         int s=u.num;

         printf("%d\n",s);

         for(int i=head[s];~i;i=nxt[i]){

             int j=point[i];

             w[j].id--;

             if(!w[j].id)q.push(w[j]);

         }

     }

 }

 int main(){

     while(scanf("%d",&n)!=EOF){

         init();

         for(int i=;i<=n;++i){

             scanf("%d%d",&w[i].p,&w[i].d);

         }

         int m;

         scanf("%d",&m);

         while(m--){

             int a,b;

             scanf("%d%d",&a,&b);

             add(a,b);

         }

         topo();

     }

     return ;

 }

之前写的是总超时时间最小的任务顺序……其实笔误了，不过并没有人告知23333自己后来看的时候才发现写错了，不过A这道题的时候并没有想错