TopCoder

Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

90.7% (88/97)

Submission's AC Ratio

52.2% (365/699)

Tags

Description

這是個困擾人類數萬年的問題:如何使每個人找到最適合的伴侶?好的對象人人追求,因此追求失敗的比例永遠超過成功率。許多人被迫選擇心目中較差的對象,也產生了大量不美滿的婚姻。

姑且假定地球上的男女一樣多,每個配對都有一個美滿度,例如甲男配乙女美滿度為 90 ,丙男配丁女美滿度為40,如此可以得到一個矩陣:

    A男  B男  C男  D男
A女  90  80  80  80
B女  80  20  10  10
C女  85  70  20  10
D女  80  60  80  10

在亞當斯密資本主義理論風行全球的二十世紀中,約翰納許提出了劃時代的創見。也因此獲得了諾貝爾經濟學獎。
他理論的一個推斷為:倘若所有人同時追求最好的對象,整體婚姻的美滿度反而會下降。舉例而言:假定這個世界是由男性來追求女性,而女性決定他的伴侶,在上面那個矩陣裡,所有人都想跟A女在一起,A女選擇了在一起後會最美滿的A男,B女則挑了剩下來最好的B男,C配C,D配D,最後四對新人的總美滿度為90+20+20+10=140。(見底線數字)
做點讓步反而會有更好的結果:假定不要每個人都競爭A女,A男配B女;B男配C女;C男配D女;D男配A女,則總美滿度為80+80+70+80=310。(見斜黑體數字)

然而在自由競爭的結婚「市場」下,每個個體無法去判斷自己該做怎麼樣的讓步以及該讓到什麼地步,因此你會發現所有人還是努力去追求自己心目中最理想的對象(你會因為跟你朋友討論對面那三個異性怎麼「分配」比較好嗎?)這或許也是離婚率不斷高升的原因之一。

到了二O五O年,政府決定要出面改善這個狀況,等數的男女資料被輸入資料庫,由電腦判斷每種配對的「美滿度」,之後透過程式運算得到最大的總「美滿度」,並根據結果替每位適婚男女安排結婚對象。

你的工作就是依照「美滿度」表找出最佳的配對方式,當然,每個人最多只能有一個伴侶,但要注意,有些人天生「顧人怨」,沒有人願意跟他/她配對,意即美滿度可以是負數,而不配對的美滿度就是0,簡而言之,如果配對起來美滿度是負數的話不如不配。身為一個程式設計師,你是否能成為稱職的「月下老人」呢?

Input Format

輸入檔包含了多筆的測試資料。每筆資料第一行為一個正整數N(1≦N≦100),接下來包含N個整數,並以一個空白鍵分隔,其中第i行的第j個整數表示女士Wi與男士Mj配對後的美滿度(可能為負整數或0)。最後一筆資料後會有一行0表示結束。

Output Format

針對每筆資料輸出一個整數,即最大的總美滿度,並以換行分隔。

Sample Input 1

3
1 2 3
1 2 3
1 2 3
4
90 80 80 80
80 20 10 10
85 70 20 10
80 60 80 10
4
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
0

Sample Output 1

6
310
0

Hints

這題目用Random不會過...(我嚐試了十幾次了= =")

※被TDYa127大大秒殺了|||

Problem Source

原TIOJ1042 / NPSC2003初賽(prob E)

2016/05/22 測資加強

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 11000 65536 262144 2