Marriage is Stable（HDOJ 1522）

2020-02-09 498次阅读 0条评论 1人点赞

稳定婚姻问题其实也算是二分图匹配，只不过是加权二分图罢了，所以我也放到了二分图这个分类，就不另外分类了

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]).

Input

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.

Output

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

Sample Output 

Albert Nancy
Brad Marcy
Chuck Laura

My Code

这题是稳定婚姻问题的模板，一般采用 Gale-Shapley算法。采用贪心的方法，每个男生表白自己没有表白过的女生中最喜欢的那个，如果那个女生没有对象，你们就匹配成功，如果有对象，但那个女生更喜欢你，那么也匹配成功，而那个被甩的男生恢复单身。这样不断循环，直到所有人都有对象。理论上应该是不会出现有人没对象的情况，所以这里这里不考虑 "Impossible" 也能过。

#include 
#include 
#include 
#include 
#include 

using namespace std;

int n;
int m[505][505], g[505][505];      //m[i][j]表示编号为i的女生对编号为j的男生的喜欢排名
//g[i][j]表示编号为i的男生，第j喜欢的女生的编号，两个数组意义不同，千万别搞错
int m_g[505], g_m[505];            //m_g[i]为编号为i的女生的对象的编号，g_m[i]为编号i的男生的对象的编号
int p[505];                        //p[i]为编号为i的男生表白次数
map mp_m, mp_g;        //将名字转换成数字编号
string sm[505], sg[505];            //数字编号对应的名字，sm是女生名字，sg是男生名字
int main()
{
    while (cin >> n)
    {
        mp_m.clear();               //多组，需清空
        mp_g.clear();
        for (int i = 1; i <= n; i++)
        {
            string s1, s2;
            cin >> s1;
            mp_g[s1] = i;           //男生编号
            sg[i] = s1;             //记录编号对应的男生名字
            for (int j = 1; j <= n; j++)
            {
                cin >> s2;
                if (!mp_m[s2])
                {
                    mp_m[s2] = j;   //女生编号
                    sm[j] = s2;     //记录编号对应的女生名字
                }
                g[i][j] = mp_m[s2];  //记录i男生第j喜欢的女生的编号
            }
        }
        for (int i = 1; i <= n; i++)
        {
            string s1, s2;
            cin >> s1;
            for (int j = 1; j <= n; j++)
            {
                cin >> s2;
                m[mp_m[s1]][mp_g[s2]] = j;  //记录女生s1对男生s2的喜欢排名
            }
        }
        bool flag = 0;
        memset(m_g, 0, sizeof(m_g));        //别忘清空
        memset(g_m, 0, sizeof(g_m));
        memset(p, 0, sizeof(p));
        while (!flag)
        {
            flag = 1;
            for (int i = 1; i <= n; i++)
            {
                if (!g_m[i] && p[i] < n)    //如果i号男生没有对象，且还有没表白过的女生
                {
                    int mm = g[i][++p[i]];  //要表白的女生
                    if (!m_g[mm])           //如果这个女生没对象
                    {
                        m_g[mm] = i;        //配对成功
                        g_m[i] = mm;
                    }
                    else if (m[mm][i] < m[mm][m_g[mm]]) //如果这个女生更喜欢你
                    {
                        g_m[m_g[mm]] = 0;       //把原来的男生甩了
                        m_g[mm] = i;            //匹配成功
                        g_m[i] = mm;
                    }
                    flag = 0;
                }
            }
        }
        /* flag = 0;                        //这边是判断匹配失败的情况，不过貌似没有这个数据点
        for (int i = 1; i <= n; i++)        //所以可以不写
            if (!g_m[i])
            {
                flag = 1;
                break;
            }
        if (flag)
            cout << "Impossible" << endl;
        else*/
        for (int i = 1; i <= n; i++)
            cout << sg[i] << ' ' << sm[g_m[i]] << endl;
    }
    return 0;
}