NTUCPC Speed Run! #1 比賽已結束，感謝大家的參與！題目連結
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
165 . 飛行航線規劃
TopCoder
Tags
Description
IOIC 國有 $n$ 個城市，第 $i$ 個城市的繁榮度為 $a_i$。而這 $n$ 個城市透過 $m$ 條公路連接，其中第 $i$ 條公路為一條從城市 $u_i$ 開往城市 $v_i$ 的單向道。此外，對於任何兩個相異城市 $u,v$，若 $u$ 可以經由公路走到 $v$，那麼不存在道路可以讓 $v$ 走到 $u$。
由於疫情的關係，為了減少不必要的人員流動，政府決定封鎖原有的公路並規劃新的飛行航線來維持城市間的貿易。然而每個城市只能開一條對外的航線飛往另一個原本能經由公路到達的城市。已知一個城市 $u$ 若開設飛往城市 $v$ 的航線則能帶來 $a_v$ 的利益。因此為了最大化 IOIC 國的總利益，對於每個城市，政府將開設一個航線飛往它原本能經由公路到達的城市中，繁華程度最高的一個城市（當然，如果一個城市無法到達任何其他城市則不會開設任何航班）。
請問在這樣的情況下， IOIC 國能得到的總利益為多少？
Input Format
輸入的第一行有兩個正整數 $n, m$，代表城市以及公路的數量。
輸入第二行有 $n$ 個以空白分隔的正整數 $a_i$ 代表第 $i$ 個城市的繁榮度。
接著 $m$ 行，每行有兩個正整數 $u_i, v_i$，代表第 $i$ 條公路的起訖城市。
- $1 \leq n \leq 100000$
- $0 \leq m \leq 200000$
- $1 \leq a_i \leq 10^ 9$
- $1 \leq u_i, v_i \leq N$
- 保證輸入的圖滿足對於任相異兩點 $u,v$，若存在 $u$ 到 $v$ 的路徑，則不存在 $v$ 到 $u$ 的路徑
Output Format
請輸出一行一個整數代表 IOIC 國能得到的總利益。
Sample Input 1
4 4
2 5 4 3
1 2
1 3
3 4
2 4
2 5 4 3
1 2
1 3
3 4
2 4
Sample Output 1
11
Sample Input 2
5 4
5 3 1 2 4
1 2
2 3
3 4
4 5
5 3 1 2 4
1 2
2 3
3 4
4 5
Sample Output 2
16
Sample Input 3
8 10
9 1 5 7 4 3 6 8
1 2
1 3
4 6
6 7
2 4
5 8
2 5
6 8
3 6
8 8
9 1 5 7 4 3 6 8
1 2
1 3
4 6
6 7
2 4
5 8
2 5
6 8
3 6
8 8
Sample Output 3
48
Hints
Problem Source
IOICamp 2022 Day2 pE
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 0~24 | $N \leq 1000, M \leq 2000$ | 30 |
| 3 | 0~137 | 無額外限制 | 70 |