Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

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

姑且假定地球上的男女一樣多，每個配對都有一個”美滿度”，例如甲男配乙女美滿度為 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。

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

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

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

輸入檔包含了多筆的測試資料。

每筆資料第一行為一個正整數N（1≦N≦100），接下來包含N個整數，並以一個空白鍵分隔，其中第ｉ行的第ｊ個整數表示女士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