稳定婚姻问题

一、稳定婚姻问题

稳定婚姻问题，Stable Marriage Problem。

什么是稳定婚姻问题？

        有N男N女，每个人都按照他对异性的喜欢程度排名。现在需要写出一个算法安排这N个男的、N个女的结婚，要求两个人的婚姻应该是稳定的。

        何为稳定？

        有两对夫妻M1 F2，M2 F1。M1心目中更喜欢F1，但是他和F2结婚了，M2心目中更喜欢F2，但是命运却让他和F1结婚了，显然这样的婚姻是不稳定的，随时都可能发生M1和F1私奔或者M2和F2私奔的情况。所以在做出匹配选择的时候（也就是结婚的时候），我们需要做出稳定的选择，以防这种情况的发生。

二、算法

        1962 年，美国数学家 David Gale 和 Lloyd Shapley 发明了一种寻找稳定婚姻的策略。不管男女各有多少人，不管他们各自的偏好如何，应用这种策略后总能得到一个稳定的婚姻搭配。换句话说，他们证明了稳定的婚姻搭配总是存在的。有趣的是，这种策略反映了现实生活中的很多真实情况。

算法中采用了男生主动追求女孩的形式。

 

1.算法步骤描述

        第一轮，每个男人都选择自己名单上排在首位的女人，并向她表白。这种时候会出现两种情况：

     （1）该女士还没有被男生追求过，则该女士接受该男生的请求。

     （2）若该女生已经接受过其他男生的追求，那么该女生会将该男士与她的现任男友进行比较，若更喜欢她的男友，那么拒绝这个人的追求，否则，抛弃其男友。

第一轮结束后，有些男人已经有女朋友了，有些男人仍然是单身。

       在第二轮追女行动中，每个单身男都从所有还没拒绝过他的女孩中选出自己最中意的那一个，并向她表白，不管她现在是否是单身。这种时候还是会遇到上面所说的两种情况，还是同样的解决方案。直到所有人都不在是单身。

2.算法正确性证明

     （1）随着轮数的增加，总有一个时候所有人都能配上对。因为男生根据自己心目中的排名依次对女士进行表白，假如有一个人没有配上对，那么这个人必定是向所有的女孩进行表白了。但是女孩只要被表白过一次，就不可能是单身，也就是说此时所有的女生都不是单身的，这与有一个人没有配上对是相悖的。所以假设不成立。该算法一定会使得所有人都能够配对成功。

     （2）随着轮数的增加，男士追求的对象越来越糟，而女士的男友则可能变得越来越好。假设男A和女1各有各自的对象，但是比起现在的对象，男A更喜欢女1，所以，在此之前男A肯定已经跟女1表白过的，并且女1拒绝了男A，也就是女1有了比男A更好的男友，不会出现私奔的情况……。

 三、实现

hdoj1435 Stable Match

稳定婚姻模板题。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define maxn 205
using namespace std;
struct point{
    int num,v;
    double x,y,z;
}Man_array[maxn],Woman_array[maxn];
struct point2{
    int num,v;
    double dis;
}A[maxn*maxn];
int n;
int nowb[maxn],nowg[maxn],V[maxn][maxn],B_g[maxn][maxn],G_b[maxn][maxn];
double calc(point p,point q){
    double xx=p.x-q.x,yy=p.y-q.y,zz=p.z-q.z;
    return sqrt(xx*xx+yy*yy+zz*zz);
}
int comp(point2 p,point2 q){
    return p.dis<q.dis || p.dis==q.dis && p.v>q.v;
}
void Stable_Marriage(){
    memset(V,0,sizeof(V));memset(nowb,-1,sizeof(nowb));memset(nowg,-1,sizeof(nowg));
    queue<int> Q;
    for (int i=0;i<n;i++) Q.push(i);
    while (!Q.empty()){
        int pre=Q.front(),res;
        Q.pop();
        for (int i=0;i<n;i++){
            int res=B_g[pre][i];
            if (V[pre][res]) continue;
            V[pre][res]=1;
            if (nowg[res]==-1){
                nowg[res]=pre;
                nowb[pre]=res;
                break;
            }
            else if (G_b[res][nowg[res]]<G_b[res][pre]){
                Q.push(nowg[res]);
                nowg[res]=pre;
                nowb[pre]=res;
                break;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while (t--){
        cin >> n;
        for (int i=0;i<n;i++){
            cin >> Man_array[i].num >> Man_array[i].v >> Man_array[i].x >> Man_array[i].y >> Man_array[i].z;
        }
        for (int i=0;i<n;i++){
            cin >> Woman_array[i].num >> Woman_array[i].v >> Woman_array[i].x >> Woman_array[i].y >> Woman_array[i].z;
        }
        //男——女 
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                A[j].dis=calc(Man_array[i],Woman_array[j]);
                A[j].v=Woman_array[j].v;
                A[j].num=j;
            }
            sort(A,A+n,comp);
            for (int j=0;j<n;j++) B_g[i][j]=A[j].num;
        }
        //女——男
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                A[j].dis=calc(Woman_array[i],Man_array[j]);
                A[j].v=Man_array[j].v;
                A[j].num=j;
            }
            sort(A,A+n,comp);
            for (int j=0;j<n;j++) G_b[i][A[j].num]=n-j+1;
        } 
        Stable_Marriage();
        for (int i=0;i<n;i++){
            cout << Man_array[i].num << " " << Woman_array[nowb[i]].num << endl;
        }
        cout << endl;
    }
    return 0;
}