图论:Gale-Shapley算法
2024-10-21 04:13:32
Gale-Shapley算法又叫做延迟认可算法,它可以解决这么一个问题
一共有N位男士和N位女士
每位男士对每位女士都有一个好感度,让他们结合成为N对夫妻,要求男士优先表白,最后问结合情况
第一轮,每个男人都选择自己名单上排在首位的女人,并向她表白。
这种时候会出现两种情况:
()该女士还没有被男生追求过,则该女士接受该男生的请求。
()若该女生已经接受过其他男生的追求,那么该女生会将该男士与她的现任男友进行比较,若更喜欢她的男友,那么拒绝这个人的追求,否则,抛弃现任……
第一轮结束后,有些男人已经有女朋友了,有些男人仍然是单身。
在第二轮追女行动中,每个单身男都从所有还没拒绝过他的女孩中选出自己最中意的那一个,并向她表白,不管她现在是否是单身。
这种时候还是会遇到上面所说的两种情况,还是同样的解决方案。直到所有人都不在是单身。
以上给出了算法的描述,下面直接给出代码,题目是POJ3487
由于这个问题没有太大变式直接套模板就好了,如果要求女士优先,那就把男女身份互换然后再套用这个模板就好了
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=;
int n;
int ml[maxn][maxn],fl[maxn][maxn],mc[maxn],fc[maxn];
int mn[maxn],fn[maxn];
queue<int> q; //没有配对的男士
int main()
{
int T;
char s[maxn];
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
//读入男士的名字,初始化都没有配对
for(int i=;i<n;i++)
{
scanf("%s",s);
mn[i]=s[]-'a';
q.push(mn[i]);
}
//将名字排序
sort(mn,mn+n);
for(int i=;i<n;i++)
{
scanf("%s",s);
fn[i]=s[]-'A';
}
//男士对女士的印象
for(int i=;i<n;i++)
{
scanf("%s",s);
for(int j=;j<n;j++)
ml[i][j]=s[j+]-'A';
}
//女士对男士的打分,n号为初始对象
for(int i=;i<n;i++)
{
scanf("%s",s);
for(int j=;j<n;j++)
fl[i][s[j+]-'a']=n-j;
fl[i][n]=;
}
//一开始男士的期望都是最喜欢的女士
memset(mc,,sizeof(mc));
//女士先初始化一个对象
for(int i=;i<n;i++)
fc[i]=n;
while(!q.empty())
{
//h=h%maxn+1;
//找出一个没有配对的男士
int m=q.front();
//男士心怡的女士
int fm=ml[m][mc[m]];
//如果当前男士比原来的男友好
if(fl[fm][m]>fl[fm][fc[fm]])
{
//脱单
q.pop();
//否则考虑下一个对象
if(fc[fm]!=n)
{
q.push(fc[fm]);
mc[fc[fm]]++;
}
//当前男友为这位男士
fc[fm]=m;
}
else mc[m]++; //如果女士拒绝,考虑下一个对象
}
for(int i=;i<n;i++)
printf("%c %c\n",mn[i]+'a',ml[mn[i]][mc[mn[i]]]+'A');
if(T) puts("");
}
return ;
}
另外记住一点如果队列不是特别正常的队列不要手写,还是STL比较稳
最新文章
- 数字格式化函数:Highcharts.numberFormat()
- Count and Say leetcode
- centos修改文件及文件夹权限
- 大白话系列之C#委托与事件讲解(三)
- 关于Winform发布时,资源文件缺失的解决方案
- SqlServer 事务日志传输
- 使用spring-amqp结合使用rabbitmq
- 浅谈HTML5拖放
- js动画学习(四)
- java 线程、线程池基本应用演示样例代码回想
- MYSQL外键的使用以及优缺点
- 自定义下拉刷新上拉加载View
- ASP.NET Core依赖注入——依赖注入最佳实践
- Python之yield简明详解
- linux环境下运行程序格式错误的问题,bash: ./helloworld: cannot execute binary file: Exec format error
- 2018.11.24 poj3261Milk Patterns(后缀数组)
- python基础之单例设计模式
- ASTER:An Attentional Scene Text Recognizer with Flexible Rectification
- vue---阻止默认表单提交的三种方法
- Shuffle&#39;m Up---poj3087
热门文章
- Altium Designer -- 精心总结
- struts2官方 中文教程 系列十四:主题Theme
- struts2官方 中文教程 系列九:Debugging Struts
- 读取Excel错误,未在本地计算机上注册 oledb.4.0
- Returning Values from Bash Functions
- Windows模拟linux终端工具Cmder+Gow
- selenide 自动化UI测试中Configuration全局配置项目
- 第十七篇 Python函数之闭包与装饰器
- Jmeter非GUI命令参数说明
- Struts2(三.用户登录状态显示及Struts2标签)