POJ 3553 Task schedule

　　原题链接：http://poj.org/problem?id=3553

　　这道题主要就是贪心思想吧，对于每个job，根据其截止时间 d从小到大排序，我们必须要尽快把dj最小的job完成掉，这样才能使max{C-d, 0}最小（因为对于最小d在没完成该工作时d使不变的，如果你先做了其他没关联的工作，只会使C变大，从而使max{C-d, 0}变大，这和题目所求刚好相反了）。因为要完成d工作会需要先完成其他工作，那么这时候dfs一下，一步一步找到其祖先打印出来即可。

　　网上有人用的拓扑排序+贪心，我表示没看懂。

 #include <stdio.h>

 #include <string.h>

 #include <vector>

 #include <queue>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 int n, m;

 struct node

 {

     int p;

     int d;

     int id;

 }job[maxn];

 vector<int> V[maxn];

 bool vis[maxn];

 bool cmp(node a, node b)

 {

     return a.d < b.d;

 }

 void dfs(int cur)

 {

     if(vis[cur])

         return ;

     vis[cur] = true;

     int k = V[cur].size();

     for(int i = ; i < k; i++)

         dfs(V[cur][i]);

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

 }

 void init()

 {

     memset(vis, false, sizeof vis);

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

         V[i].clear();

 }

 int main()

 {

     int a, b;

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

     {

         init();

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

         {

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

             job[i].id = i;

         }

         sort(job+, job+n+, cmp);

         scanf("%d", &m);

         for(int i = ; i <= m; i++)

         {

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

             V[b].push_back(a);

         }

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

             if(!vis[job[i].id])

                 dfs(job[i].id);

     }

     return ;

 }