我正在尝试在 spoj 上解决这个问题,但不断得到错误的答案。我不明白我c++
Stable Marriage Problem
Gale - Shapley algorithm
的实施有什么问题.请检查我的代码是否存在一些逻辑错误。
我使用的一些数据结构是:包含偏好顺序的 2d 数组"女人"和"男人",数组"m"使得m[i]=j
表示男人 i 嫁给了女人 j,类似数组 w' 这样w[i]=j
表示女人 i 嫁给了男人 j, 2d 数组 'mrg' 这样 mrg[i][j]=1
意味着 i 和 j 已婚, 2D 数组 'pw' 使得 pw[i][j]=k
表示男人 j 在 i th 女人的列表中具有偏好顺序 k,类似地,2d 数组 'pm' 使得 pm[i][j]=k
表示女人 j 在 i'th 男人的列表中具有偏好顺序 k。请帮助我。
#include<cstdio>
#include<iostream>
using namespace std;
main() {
int t;
scanf("%d",&t);
while(t--) {
int n;
scanf("%d",&n);
int women[n+1][n+1],men[n+1][n+1];
int m[n+1],w[n+1],mrg[n+1][n+1],pw[n+1][n+1],pm[n+1][n+1];
for(int i=1;i<=n;++i) {
m[i]=0;
w[i]=0;
for(int j=1;j<=n;++j) {
mrg[i][j]=0;
pw[i][j]=pm[i][j]=0;
}
}
for(int i=1;i<=n;++i) {
int num;
scanf("%d",&num);
for(int j=1;j<=n;++j) {
scanf("%d",&women[num][j]);
pw[num][women[num][j]]=j;
}
}
for(int i=1;i<=n;++i) {
int num;
scanf("%d",&num);
for(int j=1;j<=n;++j) {
scanf("%d",&men[num][j]);
pm[num][men[num][j]]=j;
}
}
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
int pref=men[j][i];
if(m[j]==0) {
if(w[pref]==0) {
w[pref]=j;
mrg[j][pref]=1;
m[j]=pref;
}
else if(pw[pref][w[pref]]>pw[pref][j]) {
int oldhusband=w[pref];
m[oldhusband]=0;
mrg[oldhusband][pref]=0;
w[pref]=j;
mrg[j][pref]=1;
m[j]=pref;
}
}
else if(pm[j][pref]<pm[j][m[j]]) {
if(w[pref]==0) {
int oldwife=m[j];
w[oldwife]=0;
mrg[j][oldwife]=0;
m[j]=pref;
w[pref]=j;
mrg[j][pref]=1;
}
else if(pw[pref][w[pref]]>pw[pref][j]) {
int oldhusband=w[pref];
int oldwife=m[j];
m[oldhusband]=0;
w[oldwife]=0;
w[pref]=j;
m[j]=pref;
mrg[oldhusband][pref]=0;
mrg[j][oldwife]=0;
mrg[j][pref]=1;
}
}
}
}
for(int j=1;j<=n;++j)
cout<<j<<" "<<m[j]<<endl;
}
return 0;
}
您没有完全遵循Gale Shapely算法。 http://en.wikipedia.org/wiki/Stable_marriage_problem
function stableMatching {
Initialize all m ∈ M and w ∈ W to free
while ∃ free man m who still has a woman w to propose to {
w = m's highest ranked such woman to whom he has not yet proposed
if w is free
(m, w) become engaged
else some pair (m', w) already exists
if w prefers m to m'
(m, w) become engaged
m' becomes free
else
(m', w) remain engaged
} }
如果你看一下提到的伪代码算法,你只需要为一个女人改变伴侣,如果一个更高偏好的男人向她求婚。
在你的情况下,如果一个订婚的男人得到一个更受欢迎的伴侣,你也在尝试改变他的伴侣。根据算法的想法,这永远不会发生,因为与男人订婚的女人总是比现在的女人更优先。因此,删除此部分。
此外,男性的循环应该持续到所有男性配对(不一定是n次迭代)。