e370: 翻牌
Tags : dsu graph matchings graphs
Accepted rate : 6人/12人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-09-20 20:23

Content

  這天,蝸牛老師想要來考驗他的學生,他在桌上放了 張卡牌,卡牌的正反面都各寫了一個正整數,他提出了這樣的問題:

  「如果我們可以自由選擇卡牌要正面還是反面朝上的話,那所有朝上顯現出來的數字的總和最大可以是多少呢?」

  聰明的學生們當然很快就解決掉這個問題了,於是蝸牛老師決定加高難度:

  「那如果,我們計算分數的方式改成,把朝上的數字一一加進袋子裡,如果要加進去的數字在袋子裡已經出現過了就不加進去,那最後袋子裡的數字總和最大會是多少呢?」

  學生們馬上就被難倒了,你可以幫助他們嗎?

Input

首行輸入一個整數 N (1 ≤ N ≤ 10) 代表有 張卡牌。

接下來 N 行,第 行會有兩個正整數 ai, bi (1 ≤ aibi ≤ 109),分別代表第 i 張卡牌的正面數字和反面數字。

Output

輸出最大的總和。

Sample Input
輸入範例一
3
1 2
2 3
3 4
輸入範例二
3
1 2
2 3
3 1
輸入範例三
3
1 1
2 2
3 3
輸入範例四
3
1 2
3 4
5 6
輸入範例五
3
1 2
1 2
1 2
Sample Output
輸出範例一
9
輸出範例二
6
輸出範例三
6
輸出範例四
12
輸出範例五
3
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (4%): 1.5s , <1K
不公開 測資點#1 (4%): 1.5s , <1K
不公開 測資點#2 (4%): 1.5s , <1K
不公開 測資點#3 (4%): 1.5s , <1K
不公開 測資點#4 (4%): 1.5s , <1K
不公開 測資點#5 (5%): 1.5s , <1K
不公開 測資點#6 (5%): 1.5s , <50M
不公開 測資點#7 (5%): 1.5s , <1M
不公開 測資點#8 (5%): 1.5s , <1M
不公開 測資點#9 (5%): 1.5s , <1M
不公開 測資點#10 (5%): 1.5s , <1M
不公開 測資點#11 (5%): 1.5s , <1M
不公開 測資點#12 (5%): 1.5s , <1M
不公開 測資點#13 (5%): 1.5s , <1M
不公開 測資點#14 (5%): 1.5s , <50M
不公開 測資點#15 (5%): 1.5s , <50M
不公開 測資點#16 (5%): 1.5s , <50M
不公開 測資點#17 (5%): 1.5s , <50M
不公開 測資點#18 (5%): 1.5s , <50M
不公開 測資點#19 (5%): 1.5s , <50M
不公開 測資點#20 (5%): 1.5s , <50M
Hint :

因測資超過ZJ上限500MB,所以只挑選部分測資。

日後仍有可能變動測資,若題敘或測資有問題歡迎寄信。

 

本題共有六組測試題組,條件限制如下所示。每一組可有一或多筆測試資料。

子任務

額外輸入限制

e370_00-e370_05

 ≤18,1 ≤ ai, b≤ 106 。

e370_06

 張牌的數字都不同(總共有 2N 個相異數字)

e370_07-e370_10

 N ≤1000,1 ≤ ai, b≤ 103 。

e370_11-e370_13

 N ≤1000,1 ≤ ai, b≤ 109 。

e370_14-e370_18

 N ≤106,1 ≤ ai, b≤ 106 。

e370_19-e370_20

無特別限制。

 

Tags:
dsu graph matchings graphs
出處:
108學年度板橋高中校內資訊學科能力競賽Day3_pE310573sao [管理者:
310573sao (Jiburiru)
]


ID User Problem Subject Hit Post Date
19273
lawrence910426@... (l4wr3nc3)
e370
101 2019-09-22 12:57
19252
310573sao (Jiburiru)
e370
賽後題解
169 2019-09-20 20:21