POJ 3553 Task schedule

たまにはオンラインジャッジを埋めないと腕が鈍る一方な気がしてきた。
http://poj.org/problem?id=3553

問題概要

依存関係つきのタスクを並べる。
各タスクには締め切りと所要時間が設定されているので、MAX(締め切りをオーバーした時間）が最小になるような並べ方を出力する。

解法

依存関係がない場合、締切が早い順に並べる貪欲で解ける。
きちんとした証明ではないが簡単に説明を書く。
いま、n個のものについての最適なオーダーが決まっていると仮定する。
これに、n個のどれよりも締め切りが遅いタスクTを追加する操作を考えよう。
途中で追加したとすると、後ろの商品iについてOverTimeはT.timeだけ増え、また末尾の商品のOverTimeはTを末尾に追加した場合より大きい。
末尾に追加すると、OverTimeが増えるタスクはなく末尾のOverTimeは途中追加の場合より小さいので、途中追加より悪くはならない。

よって、トポロジカルソートと上記の貪欲を組み合わせれば解ける。
実装はヒープを使うと簡単になる。

#include <vector>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int MAX_N = 50000;
vector<int> adj[MAX_N];
int p[MAX_N], d[MAX_N];
int deg[MAX_N], ord[MAX_N];
int main() {
    int n, m;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
      scanf("%d%d", p + i, d + i);
    scanf("%d", &m);
    for(int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        --u; --v;
        adj[u].push_back(v);
    }
    for(int i = 0; i < n; ++i) 
      for(size_t j = 0; j < adj[i].size(); ++j)
        ++deg[adj[i][j]];
    memset(ord, -1, sizeof(ord));
    priority_queue<pair<int, int> > que;
    int t = 0;
    for(int i = 0; i < n; ++i)
      if(deg[i] == 0)
        que.push(make_pair(d[i], i));
    while(!que.empty()) {
        int v = que.top().second; que.pop();
        ord[t++] = v;
        for(size_t j = 0; j < adj[v].size(); ++j) {
            int nv = adj[v][j];
            --deg[nv];
            if(deg[nv] == 0)
              que.push(make_pair(d[nv], nv));
        }
    }
    for(int i = 0; i < n; ++i)
      printf("%d\n", ord[i] + 1);
    return 0;
}

ところでプロコンのテンプレはC++11用にしてしまったのでPOJではテンプレなしで解いている。
別にfor文をいちいち書いたりするのがストレスになったりはしないが、なんとなく読みづらいような。