2 shunfurh shunfurh 于 2017.09.07 11:14 提问

Marriage is Stable

Problem Description
Albert, Brad, Chuck are happy bachelors who are in love with Laura, Marcy, Nancy. They all have three choices. But in fact, they do have some preference in mind. Say Albert, he likes Laura best, but that doesn't necesarily mean Laura likes him. Laura likes Chuck more than Albert. So if Albert can't marry Laura, he thinks Nancy a sensible choice. For Albert, he orders the girls Laura > Nancy > Marcy.

For the boys:

Albert: Laura > Nancy > Marcy
Brad: Marcy > Nancy > Laura
Chuck: Laura > Marcy > Nancy

For the girls:

Laura: Chuck > Albert > Brad
Marcy: Albert > Chuck > Brad
Nancy: Brad > Albert > Chuck

But if they were matched randomly, such as

Albert <-> Laura
Brad <-> Marcy
Chuck <-> Nancy

they would soon discover it's not a nice solution. For Laura, she likes Chuck instead of Albert. And what's more, Chuck likes Laura better than Nancy. So Laura and Chuck are likely to come together, leaving poor Albert and Nancy.

Now it's your turn to find a stable marriage. A stable marriage means for any boy G and girl M, with their choice m[G] and m[M], it will not happen that rank(G, M) < rank(G, m[G])and rank(M, G) < rank(M, m[M]).

Each case starts with an integer n (1 <= n <= 500), the number of matches to make.

The following n lines contain n + 1 names each, the first being name of the boy, and rest being the rank of the girls.

The following n lines are the same information for the girls.

Process to the end of file.

If there is a stable marriage, print n lines with two names on each line. You can choose any one if there are multiple solution. Print "Impossible" otherwise.

Print a blank line after each test.

Sample Input
Albert Laura Nancy Marcy
Brad Marcy Nancy Laura
Chuck Laura Marcy Nancy
Laura Chuck Albert Brad
Marcy Albert Chuck Brad
Nancy Brad Albert Chuck

Sample Output
Albert Nancy
Brad Marcy
Chuck Laura


caozhy   Ds   Rxr 2017.09.22 08:34
Csdn user default icon
稳定婚姻问题(The Stable Marriage Problem)
RT,该问题可解决n男n女配对问题:每个人有自己理想对象排名,而要使配对后不存在一对男女不是配偶且对于彼此的好感优于当前配偶。 算法流程: 1.每一轮未订婚的男士向其未求过婚的女士求婚; 2.女士若有男士X向其求婚,如该女士之前没有未婚夫,则直接将男士X作为该女士临时的未婚夫,如已有未婚夫且对该男士X的好感比未婚夫更高,则把未婚夫甩了,重新加入单身狗队列,把X作为未婚夫。 不断执行上述过程,
POJ3487 The Stable Marriage Problem
稳定匹配问题Stable Match Problem -- 稳定婚姻问题 Stable Marriage Problem
稳定匹配问题Stable Match Problem 转自:http://hi.baidu.com/revinfly/item/e48b6fbab5145bf662388e95 问题的提出         《算法》的第一堂课讲了关于稳定匹配(Stable Matching)的问题,这是一个由现实情况引出的一个很有趣的问题。假设说现有一堆学生准备到一堆公司实习,每个学生心目中对这些公司都有一个
HDU 1522 Marriage is Stable 稳定婚姻匹配
Marriage is Stable Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 60 Accepted Submission(s): 40   Problem Descripti
一个简单的例子说明stable marriage稳定婚姻匹配问题
问题描述非常简单: 有n位男士n位女士,每位男士对所有女士按照他喜欢的程度进行排名,同时,每位女士也对所有男士有一个喜爱程度排名,无并列。 比如我们现在有4位男士:m1,m2,m3,m4,和四位女士w1,w2,w3,w4(m的意思就是man男士,w的意思就是woman女士)。第一位男士对所有女士的喜爱排名为:’w3’,’w2’,’w1’,’w4’,即他最喜欢的是第三位女士w3,接着是第二位,第一
poj 3487 The Stable Marriage Problem(稳定婚姻问题)
The Stable Marriage Problem Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 2130   Accepted: 908 Description The stable marriage problem consists of matching
天天写算法之(婚姻稳定)The Stable Marriage Problem
地址:点击打开链接和上一题目一样的操作,代码:#include&amp;lt;string.h&amp;gt; #include&amp;lt;iostream&amp;gt; #include&amp;lt;stdio.h&amp;gt; #include&amp;lt;string&amp;gt; #include&amp;lt;map&amp;gt; #include&amp;lt;queue&amp;gt; using namespace std; #define N 27 char...
hdu 3081 Marriage Match II【并查集+二分+最大流Dinic+建图】
Marriage Match II Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3597    Accepted Submission(s): 1165 Problem Description Presumably,
POJ 3487(稳定婚姻问题)
Language: Default The Stable Marriage Problem Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 1941   Accepted: 827 Description 稳定婚姻系统问题如下 集合M 表示n个男性
stable marriage