d760: 10330 - Power Transmission
Tags :
Accepted rate : 84人/90人 ( 93% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-09-21 09:41

Content

DESA正在進行一項電力傳輸的計畫。在 Barisal 這個地方新建了一座發電廠,它的主要目的是提供電力給 Dhaka這座城市。由於 Dhaka 的人口數相當多,DESA 希望盡可能透過網路傳輸最大的電力給它。但是電力在傳輸時會因電阻而損失,所以他們想要使用變電裝置來達到不損失電力的目標。

每個變電裝置有不同的容量。這指的是假如一個變電裝置得到100單位的電,而它的容量只有80個單位,那麼就會損失20單位的電。並且 連接變電裝置之間的電線也是有一定的容量的,例如容量20單位的電線無法傳輸超過20單位的電。DESA 想要知道在沒有電力損失的情況下,最多可以傳輸的電力是多少。這就是你的任務。

Input

輸入含有多組測試資料。

每組測試資料的第一列,有 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。

Output
對每一組測試資料輸出一列,最多可以從Barisal傳送多少電力到Dhaka。
Sample Input
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
Sample Output
37
50
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 3.0s , <1M
Hint :
※Luckycat譯。
Tags:
出處:
UVa10330 [管理者:
asas (打不出來只好讓能幹的妹妹幫忙death~)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」