首页 > ACM题库 > HDU-杭电 > HDU 1522 Marriage is Stable-二分图-[解题报告] C++
2013
12-12

HDU 1522 Marriage is Stable-二分图-[解题报告] C++

Marriage is Stable

问题描述 :

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.

样例输入:

3
Albert Laura Nancy Marcy
Brad Marcy Nancy Laura
Chuck Laura Marcy Nancy
Laura Chuck Albert Brad
Marcy Albert Chuck Brad
Nancy Brad Albert Chuck

样例输出:

Albert Nancy
Brad Marcy
Chuck Laura

这题是一个匹配问题,一开始想用km做最佳匹配,但是图很大肯定会tle,思考无果后只能去搜搜题解,这是个经典问题吧。从http://www.cnblogs.com/drizzlecrj/archive/2008/09/12/1290176.html这里找到了相应的资料。

稳定婚姻是组合数学里面的一个问题。

问题大概是这样:有一个社团里有n个女生和n个男生,每位女生按照她的偏爱程度将男生排序,同时每位男生也按照自己的偏爱程度将女生排序。然后将这n个女生和n个男生配成完备婚姻。

如果存在两位女生A和B,两位男生a和b,使得A和a结婚,B和b结婚,但是A更偏爱b而不是a,b更偏爱A而不是B,则这个婚姻就是不稳定的,A和b可能背着别人相伴而走,因为他俩都认为,与当前配偶比起来他们更偏爱各自的新伴侣。

如果完备婚姻不是不稳定的,则称其是稳定的。通过证明,可以得到每一个n女n男的社团,都存在稳定婚姻的结论。但是这种情况只在异性的社团中存在。也就是说在同性的社团里面,稳定婚姻的存在性将不再被保证。

Gale-Shapley 算法

while  存在男人m是自由的且还没对每个女人都求过婚
      选择这个男人m
                令w是m的优先表中还没求过婚的最高排名的女人
        if  w是自由的  
            (m,w)变成约会状态
        else  w当前与m1约会
              if  w更偏爱m1而不爱m
                                  m保持自由
              else    w更偏爱m而不爱m1
                                        (m,w)变成约会状态
                    m1变成自由
              endif
                  endif
endwhile

是不是感觉很简单,用很常理的方法写的算法。

Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author
5426960 2012-02-27 23:36:05 Accepted 1522 0MS 568K 1851 B G++ xym2010
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<vector>
using namespace std;
int n,gp_boy[505][505],gp_girl[505][505],boy[505],girl[505],rank[505];
map<string,int>mp_boy,mp_girl;
string sboy[505],sgirl[505];
char s[1000];
void deal()
{
    memset(boy,0,sizeof(boy));
    memset(girl,0,sizeof(girl));
    for(int i=1;i<=n;i++)rank[i]=1;
    while(1)
    {
        int flag=0;
        for(int i=1;i<=n;i++)
        {
            if(!boy[i])
            {
                int g=gp_boy[i][rank[i]++];
                if(!girl[g])
                    boy[i]=g,girl[g]=i;
                else if(gp_girl[g][i]>gp_girl[g][girl[g]])
                        boy[girl[g]]=0,girl[g]=i,boy[i]=g;
                flag=1;
            }
        }
        if(!flag)break;
    }
    for(int i=1;i<=n;i++)
    {
        cout<<sboy[i]<<' '<<sgirl[boy[i]]<<endl;
    }
    puts("");
}
int main()
{
    while(~scanf("%d",&n))
    {
        getchar();
        mp_boy.clear(),mp_girl.clear();
        int pos=1,tem;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",s);
                sboy[i]=s,mp_boy[s]=i;
                for(int j=1;j<=n;j++)
                {
                    scanf("%s",s);
                    tem=mp_girl[s];
                    if(tem==0)
                    mp_girl[s]=tem=pos++,sgirl[tem]=s;
                    gp_boy[i][j]=tem;
                }
        }
        for(int i=0;i<n;i++)
        {
            scanf("%s",s);
            int x=mp_girl[s];
            for(int j=0;j<n;j++)
            {
                scanf("%s",s);
                int y=mp_boy[s];
                gp_girl[x][y]=n-j;
            }
        }
        deal();
    }
    return 0;
}

发现vim贴的代码会带颜色。。。。

解题报告转自:http://blog.csdn.net/xymscau/article/details/7300422


  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])