【問題E25】老問題─求最大的總美滿度。           [回前頁]

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

姑且假定地球上的男女一樣多,每個配對都有一個"美滿度",例如甲男配乙女美滿度為 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,簡而言之,如果配對起來美滿度是負數的話不如不配。身為一個程式設計師,你是否能成為稱職的「月下老人」呢?

輸入檔說明

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

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

範例輸入

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

範例輸出

6

310

0