稳定婚姻问题
2019-01-18 / Luo Jinrong   

当我最开始做稳定婚姻问题的时候，以为这就是一个普通的二分匹配问题。于是我去学习了一下二分匹配，而看二分匹配时，在《趣学算法》前面写的是用最大流求解的算法，（真是忘得一干二净），又去学学最大流的算法。学完最大流信心满满的来看二分匹配，却发现后面算法优化里面介绍的匈牙利算法，我又多学了一个算法呢。

都学完了之后，准备去A道题练练手，都说趁热打铁不是吗。结果又发现了问题——稳定婚姻是有优先级的！！！

这几天的算法感觉都白学了呢，我怎么能眼睁睁看着flag倒下！！（算了

现在真的是最终的算法了，可以A稳定婚姻的算法，用自己打的模板测试了两道题，全都是一发过，所以flag绕了我吧。

Gale-Shapley算法

算法介绍

  • 优先级：每个人对于异性都有一个喜欢程度的排序。
  • 假设男方作为主动方，算法步骤如下：
    • 在所有男性中找一个单身男性。
    • 对该男性，在其对其他女性的喜欢程度顺序表中（从最喜欢开始）找到第一个不曾拒绝他的女性表白。
    • 对该女性
      • 如果她不存在对象，则两人直接在一起。
      • 如果她存在对象，则在该女性的喜欢程度顺序表中比较当前对象和表白对象。如果更喜欢自己现在的对象，则拒绝；否则接受表白。
    • 继续寻找单身男性直至找不到单身男性为止。

可行性分析

  • 该算法一定能找到稳定的匹配吗？
  • 答案是肯定的。我们稍微分析一下，首先，所有的男性都可以按照自己喜欢的顺序向所有的异性进行一次表白，如果有m个单身男性，那么对应的就存在m个对应的单身女性，而当女性单身时，会无条件的接受表白，所以最后不会剩下单身女性。而男性数量与女性相等，所有最后也不会存在单身男性。

数据结构构造

1
2
3
4
5
6
7
struct PARTNER{
	string name;//姓名
	int next;//单身时下一个匹配目标，这是在perfect中的下标
	int current;//当前匹配目标的下标，这是在W[]或M[]中的下标，若单身则为-1
	int pCount;//被喜欢的目标个数
	int perfect[N];//喜欢程度顺序表，越喜欢排在越前面
}M[N],W[N];

这里我构造了一个结构体，里面包括姓名、下一个匹配目标、当前对象、喜欢的目标个数、喜欢程度顺序表。创建了两个结构体数组M[],W[],分别表示男性和女性。

核心算法介绍

注释已经很详细了，就不过多介绍，里面的一些函数会在模板中展示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void gale_shapley(){//算法部分
	int mid=GetFreeMan();//获取单身男性
	while(mid>=0){//若还存在单身男性
		int wid=M[mid].perfect[M[mid].next];//获取该单身男性下一个追求目标
		if(W[wid].current==-1){//下一个追求目标单身，直接在一起
			W[wid].current=mid;
			M[mid].current=wid;
		}
		else{//名花有主
			int tmid=W[wid].current;//获取女方的当前CP在M[]中的下标
			if(GetManPos(wid,mid)<GetManPos(wid,tmid)){//若女方更喜欢追求者，则与原CP分手
				M[tmid].current=-1;
				M[mid].current=wid;
				W[wid].current=mid;
			}
			++M[mid].next;//不论成功与否，不再考虑当前追求的女方，更改下一个目标
		}
		mid=GetFreeMan();//继续获取单身男性
	}
}

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
//带优先级的二分匹配
#include<iostream>
#include<vector>
#include<string>
#define INF 0x3fffffff
using namespace std;

const int N=100;//最大节点对数，根据题目修改
int n,wCount;//n表示匹配对数，wCount表示当前已创建女方个数（创建男方时使用）
struct PARTNER{
	string name;//姓名
	int next;//单身时下一个匹配目标，这是在perfect中的下标
	int current;//当前匹配目标的下标，这是在W[]或M[]中的下标，若单身则为-1
	int pCount;//被喜欢的目标个数
	int perfect[N];//喜欢程度顺序表，越喜欢排在越前面
}M[N],W[N];

int GetFreeMan(){//获取一个单身男性下标，若不存在单身男性则返回-1
	for(int i=0;i<n;i++){
		if(M[i].current==-1){
			return i;
		}
	}
	return -1;
}

int GetManPos(int wid,int mid){//获取男方mid在女方wid喜欢程度顺序表的位置，若不存在则返回INF（即超级不喜欢）
	for(int i=0;i<W[wid].pCount;i++){
		if(W[wid].perfect[i]==mid){
			return i;
		}
	}
	return INF;
}

void gale_shapley(){//算法部分
	int mid=GetFreeMan();//获取单身男性
	while(mid>=0){//若还存在单身男性
		int wid=M[mid].perfect[M[mid].next];//获取该单身男性下一个追求目标
		if(W[wid].current==-1){//下一个追求目标单身，直接在一起
			W[wid].current=mid;
			M[mid].current=wid;
		}
		else{//名花有主
			int tmid=W[wid].current;//获取女方的当前CP在M[]中的下标
			if(GetManPos(wid,mid)<GetManPos(wid,tmid)){//若女方更喜欢追求者，则与原CP分手
				M[tmid].current=-1;
				M[mid].current=wid;
				W[wid].current=mid;
			}
			++M[mid].next;//不论成功与否，不再考虑当前追求的女方，更改下一个目标
		}
		mid=GetFreeMan();//继续获取单身男性
	}
}

int GetWoman(string name){//获取名为name的女性在W[]中的下标，不存在返回-1
	for(int i=0;i<wCount;i++){
		if(name==W[i].name){
			return i;
		}
	}
	return -1;
}

int GetMan(string name){//获取名为name的男性在M[]中的下标，不存在返回-1（由于先创建了男性，一般不会不存在）
	for(int i=0;i<n;i++){
		if(name==M[i].name){
			return i;
		}
	}
	return -1;
}

void AddMan(int p){//创建一个男性
	cin>>M[p].name;//输入姓名
	M[p].current=-1;//令单身
	M[p].next=0;//追求目标从最喜欢的开始
	M[p].pCount=n;//根据题目修改，一般都等于n
	int pos=0;
	string tmp_name;
	for(int i=0;i<M[p].pCount;i++){//创建喜欢程度顺序表
		cin>>tmp_name;
		int wp=GetWoman(tmp_name);//获取女性下标
		if(wp!=-1){//存在该女性，则加入顺序表pos位置
			M[p].perfect[pos++]=wp;
		}
		else{//不存在，创建一个名为name的女性在W[wCount]位置
			W[wCount].name=tmp_name;
			M[p].perfect[pos++]=wCount++;
		}
	}
}

void AddWoman(){//创建一个女性
	string tmp_name;
	cin>>tmp_name;
	int wp=GetWoman(tmp_name);//在W[]寻找名为name的女性是否被创建
	if(wp==-1){//未找到，则新建一个，并获取该新建的下标
		W[wCount].name=tmp_name;
		wp=wCount++;
	}
	W[wp].current=-1;//令单身
	W[wp].next=0;//追求目标从最喜欢开始
	W[wp].pCount=n;//根据题目修改，一般都等于n
	int pos=0;
	for(int i=0;i<W[wp].pCount;i++){//创建喜欢程度顺序表
		cin>>tmp_name;
		int mp=GetMan(tmp_name);//获取男性下标
		if(mp!=-1){//存在则加入顺序表pos位置（一般不会出现不存在情况，根据题目判断，如果确实会出现的话，则补上该分支）
			W[wp].perfect[pos++]=mp;
		}
	}
}

void print(){//打印稳定匹配方案，根据题目要求格式修改
	for(int i=0;i<n;i++){
		cout<<i<<"("<<M[i].name<<")"<<"\t--\t"<<M[i].current<<"("<<W[M[i].current].name<<")"<<endl;
	}
}

int main(){
	while(cin>>n){
		wCount=0;
		for(int i=0;i<n;i++){
			AddMan(i);
		}
		for(int i=0;i<n;i++){
			AddWoman();
		}
		gale_shapley();
		print();
	}
}

return 0;

本文链接：
https://luojinrong.github.io/2019/01/18/稳定婚姻问题/