b437:
watersupply
Content
有一個山區。山區內分散有 N 個莊園，它們分別用 0 至 N-1 來編號。在山區最高點的那個莊園內有個水塔，本身水塔的這個莊園編號為 0。兩個莊園之間最多只有一條水管相連。正常日子中，電力供應充足，水泵可以自由選擇水管內水的流向。
但在一場山區大火過後，電力暫時未能恢復，水管亦受到破壞。
目前最急需需要的是修復供水。經過調查水管可以進行簡單的修復，但由於未有電力供應，水流只能借著地心吸力的作用，由某些莊園流到另一些莊園。當然，前題是它們之間之前必定要有水管將之相連。
為方便以下敘述，我們以水塔莊園海拔高度為標準，計算莊園 i 與水塔莊園之間海拔高度差 Di。Di 越大代表莊園 i 的海拔高度越低。若兩個莊園 i, j 之間有水管相連，則在莊園 i 的水可以流往莊園 j 若及只若 Dj ≥ Di。並且，若莊園 i 的水可以流到莊園 j，且莊園 j 的水可以流到莊園 k，則供水給莊園 i 代表可以同時供水給莊園 j 及 k。目前莊園 0 是唯一有供水的地方。
當地政府希望透過這個自然流動水的方案，儘快恢復部分莊園的用水供應，但前題是要把這些水管修復。由於水管的損毀程度不一，所以水管的修復費用會有不同。因此，當地政府希望知道若實行這個方案，最多可以供水到多少個莊園？並且其最低總水管修復費用會是多少？
Input
輸入資料的第一行上有兩個正整數 N 及 M，N 代表莊園的總數目。M 則代表總共有多少條水管。2 ≤ N ≤ 500, N < M ≤ 1000
隨後的一行上，有 N-1 個整數，它們順序代表著莊園 1 至莊園 N-1 與莊園 0 之間的海拔高度差 (Di)。
再隨後的 M 行上，每行有 3 個整數 u, v 及 C。代表莊園 u 及 v 之間有一條水管相連。若其中的一個編號為零，則代表其中一個莊園實際上是水塔。 C 代表該條水管的修復費用。C ≤ 100
Output
輸出應有一行，其上含有兩個正整數，以一個空格分開。第一個整數代表最多可以供水到多少個莊園 (包括莊園 0 在內)。第二個整數代表修復所需水管的最低價錢？
Sample Input
#1
4 4 5 4 2 1 0 50 2 0 2 1 2 3 2 3 10
Sample Output
#1
3 5
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
Hint ：
# 非官方測試數據
Tags:
出處:
MOI-S 2025
[管理者：
]
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||