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

提示：

※Luckycat譯。

標籤:

出處:

UVa 10330 [管理者： asas (向諸神與地雷醬獻上祈禱) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」