d760.
10330 - Power Transmission
內容
DESA正在進行一項電力傳輸的計畫。在 Barisal 這個地方新建了一座發電廠，它的主要目的是提供電力給 Dhaka這座城市。由於 Dhaka 的人口數相當多，DESA 希望盡可能透過網路傳輸最大的電力給它。但是電力在傳輸時會因電阻而損失，所以他們想要使用變電裝置來達到不損失電力的目標。
每個變電裝置有不同的容量。這指的是假如一個變電裝置得到100單位的電，而它的容量只有80個單位，那麼就會損失20單位的電。並且 連接變電裝置之間的電線也是有一定的容量的，例如容量20單位的電線無法傳輸超過20單位的電。DESA 想要知道在沒有電力損失的情況下，最多可以傳輸的電力是多少。這就是你的任務。
輸入說明
輸入含有多組測試資料。
每組測試資料的第一列，有 1 個正整數 N（1 <= N <= 100）代表變電裝置的數目（編號 1 到 N）。下一列有 N 個正整數代表這N個變電裝置的容量。接下來的一列有一個正整數 M，代表各變電裝置間連接電線的數目。再接下來的 M 列每列有3個正整數（i j C）。i, j 為變電裝置的編號，C 為連接 i, j 的電線的容量。電力能夠從 i 變電裝置傳輸到 j 變電裝置。再接下來的一列有2個整數B，D。B代表直接連接發電廠的變電裝置的數目，D代表直接連接到Dhaka的變電裝置的數目。這些連接的電線是特別的，他們的容量是無限大（上圖以藍粗線表示）。下一列有B+D個變電裝置的編號，前B個代表直接連接Barisal發電廠的變電裝置編號，剩下的D個為直接連接到Dhaka的變電裝置的編號。連接Barisal的變電裝置不會連接到Dhaka。
輸出說明
對每一組測試資料輸出一列，最多可以從Barisal傳送多少電力到Dhaka。
範例輸入
#1
4 10 20 30 40 6 1 2 5 1 3 10 1 4 13 2 3 5 2 4 7 3 4 20 3 1 1 2 3 4 2 50 100 1 1 2 100 1 1 1 2
範例輸出
#1
37 50
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (100%): 3.0s , <1M
公開 測資點#0 (100%): 3.0s , <1M
提示 ：
※Luckycat譯。
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 42540 |
|
d760 | 27 | 2024-09-30 21:30 |