概要

前提関係を有向グラフで表し、トポロジカルソートを行いながら各タスクの最も早い完了時刻を求めます。有向閉路が存在する場合は前提関係を満たせないため、-1 を出力します。

考察

1. 前提関係を有向グラフで表す

タスクを頂点とし、「タスク \(u\) が完了してからタスク \(v\) を開始する」という前提関係を、有向辺 \(u \to v\) で表します。

このグラフに有向閉路がある場合、すべてのタスクを完了させることはできません。例えば、\(1 \to 2 \to 3 \to 1\) という関係があると、どのタスクも他のタスクの完了を待つ必要があります。

より厳密には、閉路上の前提条件を足し合わせると、開始時刻の項が打ち消し合い、\(0 \ge A_1 + A_2 + A_3\) となります。所要時間はすべて正なので、これは矛盾です。

一方、有向閉路がなければ、前提となるタスクから順に処理することで、実行可能な開始時刻を決められます。

2. 前提タスクがすべて終わったら、すぐに開始してよい

同時に進められるタスクの個数に制限はありません。そのため、開始可能なタスクを後回しにするメリットはなく、各タスクを可能な限り早く開始するのが最適です。

タスク \(v\) の最も早い完了時刻を \(\mathrm{finish}[v]\) とします。

• 前提タスクがない場合、時刻 \(0\) に開始できるので \(\mathrm{finish}[v] = A_v\)。
• 前提タスクがある場合、そのすべてが完了する必要があるので、\(\mathrm{finish}[v] = \max_{u \to v}\mathrm{finish}[u] + A_v\)。

ここで、前提タスクの完了時刻は合計ではなく最大値を使います。前提タスク同士も並行して実行できるためです。

例えば、所要時間がそれぞれ \(3, 5, 2\) のタスク \(1, 2, 3\) があり、前提関係が \(1 \to 3\) と \(2 \to 3\) だとします。タスク \(1, 2\) はともに時刻 \(0\) に開始でき、タスク \(3\) は時刻 \(\max(3,5)=5\) に開始できます。したがって、全体の完了時刻は \(5+2=7\) です。

3. 前提タスクから順に計算する

タスクを番号順に処理しても、前提タスクの完了時刻がまだ求まっているとは限りません。また、全タスクを繰り返し走査して開始可能か調べる方法では、依存関係が長く連なる場合に \(O(N^2)\) 時間かかることがあります。

そこで、トポロジカルソートを使います。これは、有向グラフの各辺 \(u \to v\) について、必ず \(u\) を \(v\) より先に処理するような順序を求める手法です。

この順序で計算すれば、タスク \(v\) を処理するときには、すべての前提タスクの最も早い完了時刻が確定しています。

上の式で求めた時刻より早く完了することはできず、実際にその時刻で実行することもできるため、全タスクの \(\mathrm{finish}\) の最大値が答えになります。

アルゴリズム

入次数とキューを使うトポロジカルソート（Kahn 法）に、完了時刻の更新を組み合わせます。

入次数とは、その頂点に入ってくる辺の本数です。処理中の入次数は「まだ処理されていない前提タスクの個数」を表します。

1. 各前提関係 \(u \to v\) を隣接リストに追加し、\(v\) の入次数を \(1\) 増やします。
2. すべてのタスクについて、\(\mathrm{finish}[i] = A_i\) と初期化します。
3. 入次数が \(0\) のタスクをすべてキューに入れます。
4. キューが空になるまで、次を繰り返します。
   • タスク \(u\) を取り出し、処理済みタスク数を \(1\) 増やします。
   • 答えの候補を \(\mathrm{answer} = \max(\mathrm{answer}, \mathrm{finish}[u])\) で更新します。
   • 各辺 \(u \to v\) について、次の処理を行います。
     • \(\mathrm{finish}[v] = \max(\mathrm{finish}[v], \mathrm{finish}[u] + A_v)\) と更新します。
     • \(v\) の入次数を \(1\) 減らします。
     • 入次数が \(0\) になったら、\(v\) をキューに入れます。
5. 処理済みタスク数が \(N\) なら answer を出力し、そうでなければ -1 を出力します。

タスク \(v\) がキューに入る時点では、すべての前提タスクからの更新が終わっているため、\(\mathrm{finish}[v]\) は確定しています。

また、全タスクを処理できなかった場合、未処理部分には有向閉路が存在します。その場合は前提関係を満たす開始時刻を設定できません。

計算量

• 時間計算量: \(O(N+M)\)
• 空間計算量: \(O(N+M)\)

各タスクはキューに一度だけ入り、各前提関係も一度だけ処理します。隣接リスト、完了時刻、入次数、キューに必要な領域も合わせて \(O(N+M)\) です。

実装のポイント

• 完了時刻には 64 ビット整数を使う
  完了時刻は最大で所要時間の総和程度になり、\(N \times 10^9 \le 2 \times 10^{14}\) に達する可能性があります。コードでは A、finish、answer に long long を使っています。

• finish は所要時間で初期化する
  前提タスクがない場合の完了時刻は、そのタスクの所要時間そのものです。全頂点を finish[i] = A[i] としておけば、共通の更新式で処理できます。

• すべての前提タスクからの更新を受け取る
  前提タスクが複数ある場合、最後に完了するものを待つ必要があります。代入で上書きするのではなく、必ず max で更新します。

• 閉路判定には処理済みタスク数を使う
  グラフの一部だけに閉路がある場合、他のタスクは処理できることがあります。キューが空になった後、processed == N を確認する必要があります。

• \(M=0\) の場合も特別扱いは不要
  すべてのタスクを時刻 \(0\) に開始できるため、同じ処理で \(\max_i A_i\) が得られます。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<long long> A(N), finish(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        finish[i] = A[i];
    }

    vector<vector<int>> graph(N);
    vector<int> indegree(N, 0);

    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        graph[u].push_back(v);
        ++indegree[v];
    }

    queue<int> q;
    for (int i = 0; i < N; ++i) {
        if (indegree[i] == 0) q.push(i);
    }

    int processed = 0;
    long long answer = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ++processed;
        answer = max(answer, finish[u]);

        for (int v : graph[u]) {
            finish[v] = max(finish[v], finish[u] + A[v]);
            if (--indegree[v] == 0) q.push(v);
        }
    }

    cout << (processed == N ? answer : -1LL) << '\n';
    return 0;
}

---

この解説は gpt-6-astra-medium によって生成されました。