733 . 七彩繽紛銀河麵

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

apcsc apcsc-greedy

Description

面試麵屋牡丹未果的赤井心，憤而在麵屋牡丹本店對面開了一家烏龍麵，想奪取麵屋牡丹的客源。為了具備和麵屋牡丹對抗的實力，赤井心開始認真研究烏龍麵的配方。她得知了一碗烏龍麵由以下兩個要素組成：麵團配方和調味料配方。
於是赤井心備齊了 $N$ 種麵團和 $N$ 種調味料，準備大展身手，搭配出 $N$ 碗烏龍麵。她發現每種麵團都與特定一種調味料會產生「絕配」。當第 $i$ 種麵團和某種調味料是絕配，會產生 $c_i$ 的美味程度；但也可能搭配特定一種調味料後會製造出地獄組合，損失 $d_i$ 點的美味程度。
如果某組麵團和調味料的搭配不是絕配，也不是地獄組合則美味程度為 $0$。浪費食材是不可饒恕的事，因此一種麵團一定跟洽一種調味料搭配，一種調味料也跟洽一種麵團搭配。
沒有學過演算法的赤井心來找你幫忙，她聽說你是個演算法高手。你能想辦法讓總美味程度最大嗎?

Input Format

第 $1$ 行輸入 $N$，代表有 $N$ 種麵團與 $N$ 種調味料。
第 $2$ 到第 $N+1$ 行，每行有兩個數字 $a_i,c_i$，表示第 $i$ 種麵團和第 $a_i$ 種調味料會產生絕配，並且獲得 $c_i$ 美味程度。
第 $N+2$ 到第 $2N+1$ 行，每行有兩個數字 $b_i,d_i$，表示第 $i$ 種麵團和第 $b_i$ 種調味料會產生地獄組合，並且損失 $d_i$ 美味程度，若 $b_i=d_i=0$，則代表第 $i$ 種麵團不會跟任何調味料產生地獄組合。

  • $1\leq N\leq 5\times 10^ 5$
  • $1\leq a_i\leq N$
  • $0\leq b_i\leq N$
  • $0\leq c_i,d_i\leq 10^ 9$
  • $a_i\neq b_i$

Output Format

一個整數 $k$，代表最大的總美味程度。

Sample Input 1

3
2 1
1 3
1 2
0 0
0 0
0 0

Sample Output 1

4

Sample Input 2

3
2 1
1 3
1 2
3 1
3 4
3 5

Sample Output 2

2

Hints

Problem Source

第九屆高一生程式設計排名賽 pF

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~26 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 524288 65536 1 2
1 5000 524288 65536 1 2
2 5000 524288 65536 2
3 5000 524288 65536 2
4 5000 524288 65536 2
5 5000 524288 65536 2
6 5000 524288 65536 2
7 5000 524288 65536 2
8 5000 524288 65536 2
9 5000 524288 65536 2
10 5000 524288 65536 2
11 5000 524288 65536 2
12 5000 524288 65536 2
13 5000 524288 65536 2
14 5000 524288 65536 2
15 5000 524288 65536 2
16 5000 524288 65536 2
17 5000 524288 65536 2
18 5000 524288 65536 2
19 5000 524288 65536 2
20 5000 524288 65536 2
21 5000 524288 65536 2
22 5000 524288 65536 2
23 5000 524288 65536 2
24 5000 524288 65536 2
25 5000 524288 65536 2
26 5000 524288 65536 2
Submit
Back to Top