我们先来学一下稳定婚姻问题

什么是稳定婚姻问题?

有n个女士和n个男士,他们要一一进行配对。每个男士心中对这n个女士都有一个排名,同理,每个女士心里对n个男性也有一个排名。我们要做的是,在他们配对完成以后,不存在以下这种情况:女士a和男士b进行了配对,但是女士c在男士b心里的排名要高于a,而且男士b在女士c心里的排名也高于女士c当前的伴侣,因为如果出现这种情况男士b和女士c很有可能抛下现在的配对对象而“出轨”。同理女士a也不存在一个男士d,条件也是如此。

我们有一个专门的算法来解决这个问题。算法的大致过程就是男士不断地求婚,而女士不断地拒绝的过程。

在每一轮中,每个单身的男人在没有拒绝过他的女士中找到一个在他心里排名最高的女士进行表白,然后被表白的女士如果此时是单身,那么就会先接受这个男士的表白,暂时和他配对。如果这个女士已经有配对的对象,那么此时这个女士就会比较现在这个向她表白的男士和她现在的配对对象谁再她心里的排名更高,然后她会选择排名更高的那一个拒绝掉另一个。

然后我们再来看这道【LA3989】

在一个盛大的校园舞会上有n位男生和n位女生,每个人都对每个异性有一个排序,代表对他们的喜欢程度。你的任务是将男生和女生一一配对(每个人恰好有一个舞伴),使得男生u和女士v不存在以下情况 1.男生u和女生v不是舞伴;2.他们喜欢对方的程度都大于喜欢各自自己当前舞伴的程度。如果出现了2中的情况,他们可能会擅自抛下自己的舞伴,另外组成一对。

你的任务是对于每个女生,在所有可能和她跳舞的男生中,找出她最喜欢的那个。

这个题就是稳定婚姻问题的模板题了,直接套我们上面的模板的方法就可以。

code from LRJ

 #include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue> using namespace std; const int maxn=+;
int pref[maxn][maxn],order[maxn][maxn],Next[maxn];
int future_husband[maxn],future_wife[maxn];
queue<int>q;
void engage(int man,int woman){
int m=future_husband[woman];
if(m){
future_wife[m]=;
q.push(m);
}
future_wife[man]=woman;
future_husband[woman]=man;
} int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
for(int i=;i<=n;i++){
for(int j=;j<=n;j++)
scanf("%d",&pref[i][j]);//编号为i的男士第j喜欢的人
Next[i]=; //接下来应该向排名为1的女士求婚
future_wife[i]=; //没有未婚妻
q.push(i);
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
int x;
scanf("%d",&x);
order[i][x]=j; //在编号为i的女士心目中,编号为x的男性的排名
}
future_husband[i]=; //没有未婚夫
}
while(!q.empty()){
int man=q.front();q.pop();
int woman=pref[man][Next[man]++];//下一个求婚对象
if(!future_husband[woman])
engage(man,woman);
else if(order[woman][man]<order[woman][future_husband[woman]])
engage(man,woman);
else q.push(man);
}
while(!q.empty())q.pop();
for(int i=;i<=n;i++) printf("%d\n",future_wife[i]);
if(T)printf("\n");
}
return ;
}

最新文章

  1. mybatis 细粒度控制二级缓存
  2. 360demo--关于WM_GETMINMAXINFO
  3. 将数据文件从asm移到普通文件系统
  4. mongodb学习1---基本命令
  5. Java缓冲流细节
  6. hive0.13网络接口安装
  7. json转换(c#后台生成json的方法)
  8. c# 哈希表集合;函数
  9. lowerCaseTableNames
  10. (hdu step 6.3.2)Girls and Boys(比赛离开后几个人求不匹配,与邻接矩阵)
  11. MacOSX 中如何动态隐藏Dock Icon
  12. [内存管理]连续内存分配器(CMA)概述
  13. preventDefault()、stopPropagation()、return false 的区别
  14. JS最简单的字符串转数字类型
  15. gotty---用来作为k8s的web terminal,通过参数读取指定pod的日志输出
  16. day27 多态 多继承 接口类 抽象类
  17. Selenium-WebDriver驱动对照表
  18. Retrofit 使用方法
  19. Vi命令:如何删除全部内容
  20. poj 2262 Goldbach&#39;s Conjecture

热门文章

  1. Clair:CoreOS发布的开源容器漏洞分析工具
  2. jdk、jre、JVM的简单区别与联系
  3. Errors running builder &#39;DeploymentBuilder&#39; on project &#39; 解决方法
  4. 微信卡券领取页面提示签名错误,微信卡券JSAPI签名校验工具对比签名一模一样,cardExt扩展字段有问题
  5. Cannot read property &#39;setState&#39; of undefined
  6. C# datatable竖行转换的问题
  7. Erlang generic standard behaviours -- gen_server hibernate
  8. C++中const使用注意要点(一)
  9. GOF23设计模式之桥接模式(bridge)
  10. OkHttp使用方法