Menu
Article Graph

稳定婚姻问题入门

NodeKey

NodeKey

• 4 min read

第一次看了理论之后自己敲代码直接 1A ！！！蛤蛤蛤蛤！！！ 嗝～～

稳定婚姻问题的定义与求解方法详见百度百科
中文维基上写的比较简单。

简单说一下个人理解与解法。个人感觉还是挺有趣的。

稳定婚姻问题是构建在男女双方的二分图基础上的。如果对于现有的一个男女匹配，存在一个男人 a 比起现在的妻子女人 a 更喜欢 女人 b 。而与此同时，女人 b 比起现在的丈夫男人 b ，更喜欢男人 a 。那么男人 a 与 女人 b 很可能会出轨。我们称这个婚姻匹配是不稳定的。
反之，如果不存在这个会出轨的男女匹配，则称这个婚姻匹配是稳定的。

稳定婚姻问题的求法在上面的中文维基上有伪代码，我也基本上按照这个理论敲的。
略为详细的步骤如下：

  1. 为每一个男性与女性确定一个各自的异性在自己眼里的排名。但是记录方式不太一样，根据我的写法，男性需要记录的是排名第几是那个女性，女性需要记录的是这个男性排第几。
  2. 将每个男性加入队列。尝试为每个男性按排名配偶，如果这个女性暂时没有配偶，那么暂时进行匹配。否则，与她现在的配偶进行比较。给女性出轨的机会。
  3. 如果一个女性出轨了，那么她的丈夫放回队列。

其实就是不断出轨的算法啦，允许他们不断出轨，到不想出轨。

算法复杂度 ( O( n^2 ) )

下面是一个入门题 HDU 1435 Stable Match

题意：
这里的男女改成了发射站与接收站，喜欢程度改成了距离与容量。距离优先，再是容量。
让你求出一个稳定婚姻。

思路：
上面说的很清楚了啦。具体实现看代码。

AC Code

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 205;

int n;
int mrank[maxn][maxn], wrank[maxn][maxn];
int wlink[maxn];
double dis[maxn][maxn];

queue<int> que;

struct People {
    int id, cap;
    double dis;
    bool operator<(const People& a) const
    {
        if (dis != a.dis)
            return dis < a.dis;
        return cap > a.cap;
    }
} peo[maxn];

struct Point {
    int cap;
    double x, y, z;
    void input() { scanf("%*d %d %lf %lf %lf", &cap, &x, &y, &z); }
} man[maxn], woman[maxn];

inline double two(double x) { return x * x; }
inline double getDis(int a, int b) { return two(man[a].x - woman[b].x) + two(man[a].y - woman[b].y) + two(man[a].z - woman[b].z); }

void getRank()
{
    range(i, 1, n)
    {
        range(j, 1, n) peo[j] = (People){ j, woman[j].cap, dis[i][j] };
        sort(peo + 1, peo + n + 1);
        range(j, 1, n) mrank[i][j] = peo[j].id;

        range(j, 1, n) peo[j] = (People){ j, man[j].cap, dis[j][i] };
        sort(peo + 1, peo + n + 1);
        range(j, 1, n) wrank[i][peo[j].id] = j;
    }
}

void stableMatch()
{
    range(i, 1, n)
    {
        que.push(i);
        wlink[i] = -1;
    }
    while (!que.empty()) {
        int male = que.front();
        que.pop();
        range(j, 1, n)
        {
            int female = mrank[male][j];
            if (female == -1)
                continue;
            mrank[male][j] = -1;
            if (wlink[female] == -1) {
                wlink[female] = male;
                break;
            } else if (wrank[female][wlink[female]] > wrank[female][male]) {
                que.push(wlink[female]);
                wlink[female] = male;
                break;
            }
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        range(i, 1, n) man[i].input();
        range(i, 1, n) woman[i].input();
        range(i, 1, n) range(j, 1, n) dis[i][j] = sqrt(getDis(i, j));
        getRank();
        stableMatch();
        range(i, 1, n) printf("%d %d\n", wlink[i], i);
    }
    return 0;
}
Share