TopCoder

User's AC Ratio

90.0% (27/30)

Submission's AC Ratio

41.0% (59/144)

Description

有一間玩具工廠中有許多台機器,每台機器的製造功能及每天的產量皆有所不同,因此在某些機器處理後要送到其他機器繼續製造。假設每台機器一旦完成其每天的最大產量限制後就必須停機休息,且每台機器當天完成的處理不能放到隔天才交由其他機器繼續處理。現給定每台機器每天的最大產量限制,並告知某機器處理後可由那些機器接著製造處理的先後關係。已知由這些機器從原料到完成成品的處理時間皆可在一天之內達成,請你寫一個程式,由所給定的資訊,算出該工廠每天的最大成品產量。

Input Format

輸入檔案第一行為N值($N\leq 100$),表示有N台機器。
第二行包含N個正整數,以空白區分,依序表示第一台到第N台機器每天的最大生產量。所有機器的最大生產量均不超過$10^ 9$。
第三行為M值($M \leq \frac{N(N-1)}{2}$),表示有M組機器間具有接著處理的前後關係。第四行起的M行,每行包含2個正整數值A及B,以空白區分,表示編號A的機器處理過的產品,可由編號B的機器接著處理。
請注意: 有些機器沒有給定先前需處理的機器,表示其由原料開始處理。有些機器沒有接著處理的機器,表示其處理完即為成品。若機器編號A之可接著處理的機器有一台以上,表示機器A所完成處理的每個半成品可由其中任一台機器接著處理。

Output Format

輸出該工廠每天可完成的最大成品產量。

Sample Input

Sample Input #1:

9
5 7 5 4 6 5 2 5 6
12
1 4
1 5
2 3
2 6
3 4
3 5
4 8
5 7
5 9
6 7
6 9
7 8

Sample Input #2:

9
3 4 2 1 3 2 4 1 5
8
1 3
2 4
2 5
3 7
4 7
5 6
5 8
6 9

Sample Output

Sample Output #1:

11

Sample Output #2:

6

Hints

範例1說明:
可生產最多產量的一種排程為: 機器1處理5單位,機器2處理6單位,機器3處理1單位,機器4處理3單位,機器5處理3單位,機器6處理5單位,機器7處理2單位,機器8處理5單位,以及機器9處理6單位,只有機器8及9可完成最後成品,其最多共生產(5+6)=11單位。
範例2說明:
可生產最多產量的一種排程為: 機器1處理2單位,機器2處理4單位,機器3處理2單位,機器4處理1單位,機器5處理3單位,機器6處理2單位,機器7處理3單位,機器8處理1單位,以及機器9處理2單位,只有機器7, 8及9可完成最後成品,其最多共生產(3+1+2)=6單位。

Problem Source

原TIOJ1236 / TOI2006初選(prob 4)。

Subtasks

No. Testdata Range Score
1 0 7
2 1 7
3 2 7
4 3 7
5 4 7
6 5 7
7 6 7
8 7 7
9 8 7
10 9 7
11 10 7
12 11 7
13 12 7
14 13 9

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3
3 5000 65536 262144 4
4 5000 65536 262144 5
5 5000 65536 262144 6
6 5000 65536 262144 7
7 5000 65536 262144 8
8 5000 65536 262144 9
9 5000 65536 262144 10
10 5000 65536 262144 11
11 5000 65536 262144 12
12 5000 65536 262144 13
13 5000 65536 262144 14