hdu1914 稳定婚姻问题
稳定婚姻问题就是给你n个男的,n个女的,然后给你每个男生中女生的排名,和女生心目中男生的排名,然后让你匹配成n对,使婚姻稳定,假如a和b匹配,c和d匹配,如果a认为d比b好,同时d也认为a比c好,那么ad就有可能私奔,这样就导致了婚姻的不稳定,稳定婚姻就是找到一种解决方案让婚姻稳定
算法:
稳定婚姻的解决方法比较简单,通俗易懂,而且还容易实现,具体有没有固定的模板我不知道,没有去找,自己模拟的,在求解的过程中,我们先把所有的男生都加到队列里,队列里的就表示当前还单身的男生,每次从队列里拿出一个男生,然后从她最喜欢的女生开始匹配,如果当前的女生尝试追求过,那么就不用追求了,如果当前的女生没有伴侣,那么可以直接匹配上,如果有伴侣,那么就看看当前这个男生和女生之前的伴侣在那个女生中更喜欢谁,如果更喜欢当先的这个男生,那么当前男生就和这个女生匹配,女生之前匹配过的直接变成单身,被扔回队列,否则,继续找下一个女生,知道找到一个能匹配上的为止,就这样一直到队列空的时候,就已经全部匹配完成了。
正确性:
对于男生来说,每次都是从最喜欢的女生开始匹配的,遇到的第一个没人能抢走的并且稳定的就是自己最终伴侣,也就是说如果之前追求过的女生被别人抢走了,那么他将永远抢不会来,因为对于女生来说,第一次被男士按照自己的意愿选择之后,每次变更匹配对象都是在自己心目中更加喜欢的,所以一旦他放弃了某个男生,那么那个男生就没希望在和他匹配,这样男生是从最优的选的,保证男生不会出轨,女生每次都是在选择她的男生中选择最优的,这样也保证了女生最后没有怨言,这样的话,最后的到的婚姻就是稳定的,至于稳定婚姻,肯定会有稳定方案,这个我暂时证明不了.<1962年,美国数学家
David Gale 和 Lloyd Shapley是这两个人发明的方法,并且证明了稳定婚姻一定会有解>。
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define N 30
using namespace std;
typedef struct
{
char a ,b;
}NODE;
NODE Ans[N];
int map[N][N] ,G_b[N][N];
int nowb[N] ,nowg[N];
char nameb[N] ,nameg[N];
int mark[N][N] ,ID[200];
bool camp(NODE a ,NODE b)
{
return a.a < b.a;
}
void Marr(int n)
{
queue<int>q;
for(int i = 1 ;i <= n ;i ++)
q.push(i);
memset(mark ,0 ,sizeof(mark));
memset(nowb ,255 ,sizeof(nowb));
memset(nowg ,255 ,sizeof(nowg));
while(!q.empty())
{
int xin ,tou = q.front();
q.pop();
for(int i = 1 ;i <= n ;i ++)
{
xin = map[tou][i];
if(mark[tou][xin]) continue;
mark[tou][xin] = 1;
if(nowg[xin] == -1)
{
nowg[xin] = tou;
nowb[tou] = xin;
break;
}
else
{
if(G_b[xin][tou] > G_b[xin][nowg[xin]])
{
q.push(nowg[xin]);
nowg[xin] = tou;
nowb[tou] = xin;
break;
}
}
}
}
return ;
}
int main ()
{
int t ,n ,i ,j;
char str[30];
scanf("%d" ,&t);
while(t--)
{
scanf("%d" ,&n);
getchar();
for(i = 1 ;i <= n ;i ++)
{
scanf("%s" ,str);
ID[str[0]] = i;
nameb[i] = str[0];
}
for(i = 1 ;i <= n ;i ++)
{
scanf("%s" ,str);
ID[str[0]] = i;
nameg[i] = str[0];
}
for(i = 1 ;i <= n ;i ++)
{
scanf("%s" ,str);
for(j = 2 ;j <= n + 1 ;j ++)
map[ID[str[0]]][j-1] = ID[str[j]];
}
for(i = 1 ;i <= n ;i ++)
{
scanf("%s" ,str);
for(j = 2 ;j <= n + 1 ;j ++)
G_b[ID[str[0]]][ID[str[j]]] = n - j + 2;
}
Marr(n);
for(i = 1 ;i <= n ;i ++)
Ans[i].a = nameb[i] ,Ans[i].b = nameg[nowb[i]];
sort(Ans + 1 ,Ans + n + 1 ,camp);
for(i = 1 ;i <= n ;i ++)
printf("%c %c\n" ,Ans[i].a ,Ans[i].b);
if(t) printf("\n");
}
return 0;
}
最新文章
- go语言注释
- Intellij IDEA 快捷键
- Python迭代器,可迭代对象,生成器
- mount img
- angularjs的三目运算
- 11、java中的模板方法设计模式
- 如何正确使用Cocoapods
- TCP连接状态与2MSL等待时间
- IIS网站服务器性能优化指南(转载)
- apns-http2-php,苹果push升级到http2
- MVC4多语言IHttpModule实现
- [Bhatia.Matrix Analysis.Solutions to Exercises and Problems]ExI.3.6
- 图论(KM算法,脑洞题):HNOI 2014 画框(frame)
- Nagios设置只监控不报警
- nginx整合tomcat集群并做session共享----测试案例
- mac系统webstorm快捷键
- 对Python这门课程的理解。
- 20175312 2018-2019-2 《Java程序设计》第6周学习总结
- Skflow mac安装 for tensorflow-0.8.0
- 创建一个Maven Web应用程序
热门文章
- 使用windbg定位内存问题【入门级】
- 基于4H-SIC的先进集成电路用n型LDMOS晶体管
- Debezium实现多数据源迁移(一)
- android底部导航栏小结
- 安装VMTools失败的三类解决方法(Windows、Linux、MacOs)
- PTA 二叉树的三种遍历(先序、中序和后序)
- 我的xshell配色方案,绿色/护眼/留存/备份
- 安装mongoDB出现的问题:无法启动
- [Fundamental of Power Electronics]-PART I-3.稳态等效电路建模,损耗和效率-3.5/3.6 示例:Boost变换器中包含的半导体传导损耗/要点小结
- matplotlib安装问题解决