Task (UVa Live Archive North America 2010 - Rocky Mountain)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=408&page=show_problem&problem=2886

問題

n個タスクがある。以下の2つのタイプの制約ある。

タスクiはタスクjの終了後A分以降にやらなければならない。
タスクiはタスクjの終了後A分以内ににやれなければならない。

このような制約がm個あるとき全てのタスクを終了できるか判定せよ。終了できるときはどのタイミングでタスクを行えばいいか答えよ。
1<=n<=100
A<=150

解法

まずトポロジカルソートができない場合は明らかに不可能。制約を変形すると一つ目の制約は $t_j-A\ge t_i$ 、２つ目の制約は $t_i+A\ge t_j,t_j\ge t_i$ となる。これは最短路問題の制約とみなすことができ、このグラフ上に負閉路が無い場合条件を満たす割り当てが存在する。条件を満たす割り当ては、てきとうにこの条件から収束するまでループを回せば求まる。