1 条题解

  • 1
    @ 2021-6-30 13:44:30

    可能更好的阅读体验!

    Stable Matching问题

    假设有 nn 个男生,nn个女生 (n103)~(n \le 10^3),每个人都在自己心中对 nn 个异性有一定的心仪程度排序。

    我们定义一个Unstable matching为:如果存在一对不是情侣的男女符合以下情况:

    对于该男,该女在他的心仪列表中处于现任女友的前面,对于该女,该男在他的心仪列表中亦处于现任男友的前面,那么这对男女必然有私奔的倾向、、

    这样的情景即为Unstable matching。反之,若不存在这样一对有私奔倾向的男女,即为Stable matching。

    现在,我们的任务就是构造一种Stable Matching。

    Gale-Shapley算法:

    (没错 Gale-Shapley 是两个老哥的名字)

    1、nn个男生去匹配他们的最心仪女生;

    2、所有女生挑选喜欢他中的最心仪的男生;

    3、被拒绝的男生把女生从心仪列表里面删掉(伤心了);

    4、之后男生再选择最心仪的女生,女生依然选择向他表白的最心仪的男生(可以淘汰原来的);

    PS:这里有一个很重要的特点:一旦一位女性找到配偶,她将不会再单身,只会替换成更好的(下文会提到)。

    伪代码:

    首先初始化所有男生的状态为自由
    
    while 当男生没有未曾被匹配过,并且也没有向所有女生表白过{
    
    每个男生按照对女生的喜欢程度选择舞伴
    
    if 女生未被匹配到,则与男生进行配对
    
    if 女生与已匹配的男生相比更喜欢当前的这个男生,则拆散重新匹配
    else 该女生拒绝成为男生的舞伴
    
    }
    

    一、正确性证明:


    先来考虑一下存不存在匹配:

    假设:存在男性 Z 在算法终止后仍然未匹配到女性(孤独终老)

    由此可知,一定有一位女性,假设为 A,也没有匹配到男性(抵制一夫多妻制

    根据算法,一位单身女性一定会同意向她求婚的男性,且女性一旦有配偶就不会再次单身,所以女性 A 一定没有被求过婚

    根据算法 while 循环条件,男性 Z 一定向所有女性求过婚算法才会终止

    因此男性 Z 向女性 A 求过婚

    产生矛盾,假设不成立,证明完毕

    考虑 BiB_i 匹配到 GiG_iBjB_j 匹配到 GjG_j 并且是一个不稳定匹配。

    那么就有 BiB_i 更喜欢 GjG_jGjG_j更喜欢BiB_i

    那么 BiB_i 一定会在 GiG_i 之前先选择向 GjG_j 表白,而 GjG_j 也会同意(不稳定情况的定义),但是 GjG_j 最后却是跟 BjB_j 走了,这是违反我们的定义的(双方互相喜欢,女方却选择了一个更差的男生,不科学啊)

    二、时间复杂度


    在最差情况下,显然是 O(n2)O(n^2) 的。。

    三、一个有趣的更强的结论


    我们直接给出结论:

    所有男生最后找到的一定是最佳的伴侣,而所有女生找到的一定是最差的伴侣。

    咳咳,听起来感觉很离谱,因为男生有可能因为女生找到了更好的伴侣而被抛弃(惨)

    诶,但是我们理性分析一波:

    对于男生 A,

    设最后他的女友是在他当初的心仪列表的第i位,那么在i位之前的那些女生,他是怎么追也追不到的:

    因为即使那个女生X,也必然会有比他心仪的对象——男生Y,

    而男生Y既然在当时向该女生表白,表明他认为比Y更好的女生都拒绝了他,而如果Y也拒绝了他,他最后在一起的女生必定排在Y之后。

    所以,X 和 Y 是注定要在一起的,男生 A 选择女生X只是造成了一个 Unstable Matching。

    诶,所以嘛,男生没有追到的那些女生,都是他太逊了硬实力不够,那么换句话说,他最后追到的女生是他最好的选择了。

    女生最劣分配同理也可以证明。

    这是一种感性的证明方法,意会即可。

    四、代码:

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1005;
    
    int n;
    int Map_Man[N][N],Map_Woman[N][N];
    int Man_Partner[N],Woman_Partner[N];
    int Propose[N];		//男生的求婚目标(第几顺位的女生) 
    queue <int> Free_Man;		//未婚男生队列(男生追女生) 
    
    inline int read(){
        int x=0,f=1;
    	char ch=getchar();
        while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
        while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
        return x*f;
    }
    
    int main(){
    	n=read();
    	memset(Man_Partner,-1,sizeof(Man_Partner));
    	memset(Woman_Partner,-1,sizeof(Woman_Partner));
    	
    	for (int i=1;i<=n;i++)
    		for (int j=1;j<=n;j++)
    			Map_Man[i][j]=read();	
    	//第i个男生的第j顺位心仪女生是Map_Man[i][j] 
    	
    	for (int i=1;i<=n;i++)
    		for (int j=1;j<=n;j++){
    			int x=read();
    			Map_Woman[i][x]=j;
    		}
    	//注意:第i个女生对第j个男生的心仪程度是Map_Woman[i][j] 
    	
    	for (int i=1;i<=n;i++)
    		Free_Man.push(i);		//将所有男生加入未婚男生队列
    	
    	while (!Free_Man.empty()){
    		int i=Free_Man.front();
    		Propose[i]++;
    		int like=Map_Man[i][Propose[i]];		//like为求婚目标 
    		if (Woman_Partner[like]==-1){	//如果女生未婚 
    			Woman_Partner[like]=i;		//互相选定
    			Man_Partner[i]=like;
    			Free_Man.pop();		//退出未婚队列 
    		}
    		else if (Map_Woman[like][i]<Map_Woman[like][Woman_Partner[like]]){		//女生找到了更好的男生 
    			Man_Partner[Woman_Partner[like]]=-1;		//男生被淘汰,进入未婚状态
    			Free_Man.push(Woman_Partner[like]); 
    			Woman_Partner[like]=i;		//互相选定
    			Man_Partner[i]=like;
    			Free_Man.pop();
    		}
    	}
    	
    	for (int i=1;i<=n;i++)
    		printf("%d\n",Woman_Partner[i]);
    	return 0;
    }
    

    部分内容引用自:

    1.https://www.cnblogs.com/jielongAI/p/9463029.html
    2.https://blog.csdn.net/alwaysik/article/details/78949250
    3.https://zhuanlan.zhihu.com/p/225925804
    • 1

    信息

    ID
    62
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    21
    已通过
    14
    上传者