注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1522 Marriage is Stable  

2014-03-05 20:52:38|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=1522
稳定婚姻问题,已知男士喜欢的女士,喜欢程度递减;女士喜欢的男士,喜欢程度递减。问如何配对,使得能达到稳定婚姻,也就是说,除了自己的配偶之外,我爱的人不爱我,爱我的人我不爱。
Gale-Shapley算法:
    先对所有男士进行落选标记,称其为自由男。当存在自由男时,进行以下操作:
    ① 每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士;
    ② 每一位女士将正在追求她的自由男与其当前男友进行比较,选择其中排名优先的男士作为其男友,即若自由男优于当前男友,则抛弃前男友;否则保留其男友,拒绝自由男。
    ③ 若某男士被其女友抛弃,重新变成自由男。

int n,libMan[N][N],libLady[N][N+1],man[N+1],lady[N];
map<string,int>Mb,Mg;
map<string,int>::iterator it;
string nameboy[510],namegirl[510];

void init()
{
string str;
Mb.clear();Mg.clear();
cin>>nameboy[0];Mb[nameboy[0]]=0;
for(int i=0;i<n;i++)
{
cin>>namegirl[i];
Mg[namegirl[i]]=i;
libMan[0][i]=i;
}
for(int i=1;i<n;i++)
{
cin>>nameboy[i];
Mb[nameboy[i]]=i;
for(int j=0;j<n;j++)
{
cin>>str;
libMan[i][j]=Mg[str];
}
}
for(int i=0;i<n;i++)
{
cin>>str;
int t=Mg[str];
for(int j=0;j<n;j++)
{
cin>>str;
libLady[t][j]=Mb[str];
}
}
}

bool ChangeFriend(int v,int oldF,int newF)
{
for(int i=0;i<=n;i++)
{
if(libLady[v][i] == oldF)
{
oldF=i;
break;
}
}
for(int i=0;i<=n;i++)
{
if(libLady[v][i] == newF)
{
newF=i;
break;
}
}
return oldF > newF;
}

void Gale_Shapley()
{
memset(man,0,sizeof(man));
for(int i=0;i<n;i++)
lady[i]=n;
int i=0;
while(i < n) //第一个男士开始选
{
int v=libMan[i][man[i]]; //第i个男士喜欢第v个女士
if(i == lady[v]) //i号男就是v号女当前男友,跳过
i++;
else if(ChangeFriend(v,lady[v],i)) //如果i号男比v号女当前男友优秀,则v抛弃前男友,重新选择
{
int t=lady[v]; //t存储前男友序号
man[lady[v]]++; //抛弃前男友,前男友选择其“次喜欢女”
lady[v]=i; //选择i号男为新男友
if(t > i) //前男友t在新男友i之后,则处理下一个男士
i++;
else //否则先处理前男友t
i=t;
}
else //继续处理i号男的“次喜欢女”
man[i]++;
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
while(sf(n)!=EOF)
{
init();
Gale_Shapley();
for(int i=0;i<n;i++)
{
cout<<nameboy[i]<<" ";
cout<<namegirl[libMan[i][man[i]]]<<endl;
}
}
return 0;
}


  评论这张
 
阅读(38)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017