AOV 最早完工時間 (AP325 Q-7-7)

某個計劃有 \(n\) 項工作，以 \(1 \sim n\) 編號，工作之間有前置關係，我們用一個點代表一項工作，以邊 \((a, b)\) 表示 \(a\) 是 \(b\) 的前置工作，也就是說 \(a\) 完成之後，工作 \(b\) 才能開始。每一項工作 \(v\) 有一個需求的工作時間 \(w[v]\)，代表該工作至少需要耗時 \(w[v]\) 才能完成。

本題要計算此計畫的最早完工時間，也就是計畫開始後，最早可以完成所有工作的時間。此外，對於某個工作，如果該工作的任何延誤都會讓整個計畫的最早完工時間延後，這個工作就稱為關鍵工作，否則稱為非關鍵工作。請計算哪些工作是關鍵工作。

舉例來說，\(n = 3\)，前置關係有 \((1, 3)\) 與 \((2, 3)\)，代表工作 \(1\) 完成後才可以開始工作 \(3\)，相同的，工作 \(2\) 完成後才可以開始工作 \(3\)。需求工時為 \(w[1] = 1\)、\(w[2] = 3\)、\(w[3] = 4\)。我們可以看得出，工作 \(1\) 與 \(2\) 可以一起開始平行作業，在時間 \(1\) 時可以完成工作 \(1\)，時間 \(3\) 時可以完成工作 \(2\)，因此工作 \(3\) 最早可以開始的時間是 \(3\)，而最早的完工時間是 \(7\)。這三項工作中，工作 \(2\) 與 \(3\) 是關鍵工作，但工作 \(1\) 不是，因為工作 \(1\) 只要不花超過 \(3\) 的工時（延誤超過 \(2\)），並不會影響整個計劃的最早完工時間。

輸入格式

第一行是兩個正整數 \(n\) 與 \(m\)，代表工作數與前置關係數，點以 \(1 \sim n\) 編號；第二行是 \(n\) 個正整數，依序代表每一個工作的需求工時 \(w[v]\)；接下來有 \(m\) 行，每行兩個整數 \(u\) 與 \(v\)，代表 \(u\) 是 \(v\) 的前置工作。

限制

• \(1 \le n \le 10^4\)。
• \(1 \le m \le 10^5\)。
• \(1 \le w[v] \le 10^3\)。
• \(1 \le u, v \le n\)，\(u \ne v\)；同一組前置關係不會重複出現。
• 輸入保證有解（前置關係沒有循環）。

輸出格式

第一行輸出最早完工時間，第二行輸出哪些工作是關鍵工作，輸出時依照工作的編號由小到大，相鄰兩數字之間以一個空白分隔。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

3 2
1 3 4
1 3
2 3

範例輸出 1

7
2 3

範例輸入 2

4 4
1 2 3 4
1 2
1 3
1 4
3 4

範例輸出 2

8
1 3 4

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 7 章 Q-7-7，第 246 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。