[ZJ][KM算法] d210. 老問題
內容 ：
這是個困擾人類數萬年的問題：如何使每個人找到最適合的伴侶？好的對象人人追求，因此追求失敗的比例永遠超過成功率。許多人被迫選擇心目中較差的對象，也產生了大量不美滿的婚姻。
姑且假定地球上的男女一樣多，每個配對都有一個”美滿度”，例如甲男配乙女美滿度為 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
提示
：
出處
：
< 0 的部分當作 0
#include <stdio.h>
#include <string.h>
int W[105][105], N;
int mx[105], my[105]; // match arr
int lx[105], ly[105]; // label arr
int x[105], y[105]; // used arr
int hungary(int nd) {
int i;
x[nd] = 1;
for(i = 1; i <= N; i++) {
if(y[i] == 0 && W[nd][i] == lx[nd]+ly[i]) {
y[i] = 1;
if(my[i] == 0 || hungary(my[i])) {
my[i] = nd;
return 1;
}
}
}
return 0;
}
int KM() {
int i, j, k, d;
memset(mx, 0, sizeof(mx));
memset(my, 0, sizeof(my));
memset(lx, 0, sizeof(lx));
memset(ly, 0, sizeof(ly));
for(i = 1; i <= N; i++)
for(j = 1; j <= N; j++)
lx[i] = lx[i] > W[i][j] ? lx[i] : W[i][j];
for(i = 1; i <= N; i++) {
while(1) {
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
if(hungary(i)) break;
d = 0xfffffff;
for(j = 1; j <= N; j++) {
if(x[j]) {
for(k = 1; k <= N; k++)
if(!y[k])
d = d < lx[j]+ly[k]-W[j][k] ?
d : lx[j]+ly[k]-W[j][k];
}
}
if(d == 0xfffffff) break;
for(j = 1; j <= N; j++) {
if(x[j]) lx[j] -= d;
if(y[j]) ly[j] += d;
}
}
}
int res = 0;
for(i = 1; i <= N; i++) {
if(my[i])
res += W[my[i]][i];
}
return res < 0 ? 0 : res;
}
int main() {
int n;
while(scanf("%d", &n) == 1 && n) {
N = n;
int i, j;
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
scanf("%d", &W[i][j]);
if(W[i][j] < 0)
W[i][j] = 0;
}
}
printf("%d\n", KM());
}
return 0;
}