算法的優雅（五）：平衡的愛情

首先，關于這個問題我以前寫過的，不過這次想細緻的整理一下，算法高手可以無視了，畢竟二分圖比對問題都太基礎了.....準備工作或者考研的可以看看，圖論問題還是很不錯的question.

二分圖穩定比對是圖論的一種，也可以算是網絡流的一種特型，至于網絡流的問題，以後會開一章去讨論的，而這章我們主要讨論這個有趣的問題。

在大學戀愛中，我們不得不面對一個問題，那就是被撬了.....被撬了主要原因是你對象喜愛第三者的程度大于你，如果第三者有對象，那麼他喜愛他對象的程度小于你對象，我們可以将這個簡化成一個模型。

在一個社團裡有n位女士和n位男士，這樣是為了防止單身的出現。每位女士按照其對每位男士作為配偶的偏愛程度給每位男士排名。不允許并列名次出現，是以，如果一位女士在兩位男士之間分不出差别，我們還是要求她表示出某種偏愛。這種偏愛應是純順序的，這樣每位女士将這些男士排成順序1，2，3....，n。類似地，每位男士也将這些女士排成順序1，2，3...，n。使這些男士和女士配成完備婚姻的方式有n！種。如果存在兩位女士A和B及兩位男士a和b，使得

1.A和a結婚。

2.B和b結婚。

3.A更偏愛b（名次更優先）而非a。

4.b更偏愛A而非B。

那麼我們說這個完備的婚姻是不穩定的。是以，在不穩定的完備婚姻中，A和b可能背着别人相伴逃走，因為他倆都認為，與目前配偶比起來每人都更偏愛各自的新伴侶。是以，一男一女以對他們雙方都有利的方式共同行動而打亂婚姻的情況下，這種完備婚姻是“不穩定的”。如果完備婚姻不是不穩定的，則稱其為穩定的。由此産生的第一個問題是：是否總存在穩定的完備婚姻？

再一次用二分圖來為這個問題建立數學模型。另G=（X，Y）是一個二分圖，其中

                                      X={w1,w2,......,wn}

為n位女士的集合，而

                                      Y={m1,m2,.....,mn}

為n為男士的集合。将每一個女頂點（女士在左邊）連結到每一個男頂點（男士在右邊）。所得的二分圖在包含雙方頂點集之間的所有可能的邊的意義下是完備的（也就是完全二分圖）。對應每條邊{wi,mj}，存在一個數對p，q，其中p表示在wi給男士排序中mj的位置，q表示在mj給女士排序中wi的位置。這些女士和男士的完全婚姻對應二分圖G的（n條邊的）完美比對。

在記法上，使用優先秩評定矩陣所提供的模型會更友善。該矩陣為一n行n列的陣列，n行對應每一位女士w1，w2，....，wn，n列對應每一位男士m1，m2，....，mn。在第i行和第j列交叉位置處放上分别代表wi給mj排的名次和mj給wi排的名次的數對p，q。一個完備婚姻對應該矩陣上n個位置的集合，該集合恰好包含每一行的一個位置和每一列的一個位置（經典的N車問題）。

對于每一個優先秩評定矩陣都存在穩定的完備婚姻證明：

我們定義一中确定完備婚姻的算法——延遲認可算法（Gale-Shapley算法）

從每一個女士被标記落選記号開始。

當存在落選女士時，做：

1.每一位落選的女士在所有尚未拒絕她的男士中選擇一位被她排名最優先的男士。

2.每一位男士在所有已經選擇他并且他尚未拒絕的女士中挑選被他排名最優先的女士，對她推遲決定，并于此時拒絕其餘女士。

于是，在算法執行期間，女士向男士求婚（小受？！），一些男女訂婚，但是，如果收到更好的求婚，男士可以悔婚。一旦男士訂婚，他就在算法執行始終保持訂婚狀态，但是他的未婚妻可以改變；在他看來這種改變總是一中改進。然而，女士則在算法執行期間可以訂婚若幹次；每一次新的訂婚對她來說都将導緻更不理想的伴侶。從算法的描述得出，隻要不存在被拒絕的女士，那麼每一位男士就恰與一位女士訂婚，并且由于男女人數相同，每一位女士也恰與一位男士訂婚。現在将每一位男士與他訂婚的女士配成一對并得到一種完備婚姻。現在我們證明該完備婚姻是穩定的。

考慮女士A和B及男士a和b，使A和a配對，B和b配對，但是A更偏愛b而不是a。我們證明b不可能比起偏愛B來更偏愛A。由于在算法的某個階段A在a，b間更偏愛b，A選擇b，但A因為b将某位女士排的更優先而被b拒絕。但是，在算法過程中與男士b配對的女士實際上至少與他拒絕過的任何女士有同等級的優先級。既然A被b拒絕過，b必然更偏愛B而不是A。是以，不存在不穩定的配對，該完備婚姻是穩定的。

上面的模拟過程是完全按照社會情況模拟的，女生大部分處于挑選狀态，而男生大多處在被動的狀态，不過像定親和女追男是存在的，不過由上面模拟過程可以看出來，如果想讓該部分達到穩定，那麼女生每次因為配偶不滿意而發生改變的時候都會遇到更糟糕的配偶，但如果得到更優秀的配偶那麼必然存在不穩定因素了，是以，這也是一種教育啊.......

代碼：

#include <cstring>
#include <stdio.h>
#include <string>
#include <cmath>  
#include <queue>   
#include <map>  
#include <memory>
#include <iostream>
using namespace std;
map<string, int> bmap, gmap;
string bname[501], gname[501];
int bpre[501[501];    //used to store boys' prefrence, bpre[i][j] = k means to boy i, he ranks the girl k in jth place, the girl k is his jth choice.
int gpre[501][501];    //used to store girls' prefrence, gre[i][j] = k means to girl i, she ranks the boy j in the kth place
                    //(different from the storing way of bpre[][], because to boys, they traverse girls from highest to lowest; 
                    //but to girls, they need to quickly get to know one boy's rank)
int gres[501];    //used to store girls' result, gres[i]=j means girl i is with boy j
int bres[501];
char input[1500];
int n;
queue<int> bqueue;

int main(){
    while(~scanf("%d",&n)){
        memset(gres,-1,sizeof gres);
        memset(bres,-1,sizeof bres);
        getchar();
        bmap.clear();
        gmap.clear();
        int gcount = 0, i = 0, j = 0;
        int index = 0;
        for(i = 1;i <= n;i++){
            scanf("%s", input);
            bname[i] = input;
            bmap[input] = i;
            bqueue.push(i);
            bpre[i][0] = 1;    //b[i][0] store thes ranking number of the girl whom this boy is asking, every boy starts from the 1st girl.
            for(j = 1;j <= n;j++){
                scanf("%s",input);
                if(gmap[input] == 0){
                    index++;
                    gmap[input] = index;
                    gname[index] = input;
                }
                bpre[i][j] = gmap[input];
            }
        }
        for(i = 1;i <= n;i++){
            scanf("%s", input);
            int gindex = gmap[input];
            for(j = 1;j <= n;j++){
                scanf("%s",input);
                gpre[gindex][bmap[input]] = j; //store the rank, the smaller, the higher the propriety will be.
            }
        }
        int bindex = 0, gaskindex = 0;
        while(!bqueue.empty()){
            bindex = bqueue.front();
            //cout << "current boy's name: "<< bname[bindex] <<endl;
            bqueue.pop();
            gaskindex = bpre[bindex][bpre[bindex][0]];
            if(gres[gaskindex] < 0){
                gres[gaskindex] = bindex;
                bres[bindex] = gaskindex;
            }else if(gpre[gaskindex][bindex] < gpre[gaskindex][gres[gaskindex]]){
                bqueue.push(gres[gaskindex]);
                bpre[gres[gaskindex]][0] = (bpre[gres[gaskindex]][0]+1) % (n+1);
                gres[gaskindex] = bindex;
                bres[bindex] = gaskindex;
            }else{
                bqueue.push(bindex);
                bpre[bindex][0] = (bpre[bindex][0]+1) % (n+1);
            }
        }
        for(i = 1;i <=n ;i++){
            cout<<bname[i]<<' '<<gname[bres[i]]<<endl;
        }
    }
    return 0;
}