稳定婚姻问题

POJ 1904 King’s Quest

Posted on

由已知婚姻匹配求出所有可出轨匹配。
因为稳定婚姻问题中的匹配都是完美匹配,因此也可以换一种说法,已知一个完美匹配,求出所有完美匹配。

这道题或许可能是我这辈子做的最后一道稳定婚姻问题……因为本来出的就少,感觉都是套路……
求稳定婚姻就是模拟的板子,判定和所有出轨匹配就是tarjan缩点……

尽管如此,但还是不得不学啊……

题意:
一个国王有很多个儿子,这些儿子有很多个喜欢的女孩。国王把这些女孩都找了过来,刚好儿子和女孩的数量相同。所以只能一夫一妻了。
国王要大臣给个可行方案,大臣给了。国王又要所有可行方案。大臣就烧脑子了。

儿子最多2000个……囧……厉害厉害

思路:
其实方法的话……基本还是和稳定婚姻的判定是一样的。稳定婚姻判定点这里
在求出所有强联通分量之后,找出男性的所有可婚配配偶 和 与他在同一个强联通分量的女性的交集。
从小到大输出这个交集就是我们要求的答案。

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;

const int maxn = 4005;
const int maxm = 2e5 + maxn + 5;

int n, m;

int head[maxn], idx;
struct node {
    int to;
    int next;
} edges[maxm];

void addEdge(int u, int v)
{
    edges[idx] = (node){ v, head[u] };
    head[u] = idx++;
}

int scc, top, vis_time;
int dfn[maxn], low[maxn], in[maxn], color[maxn], st[maxn], ans[maxn];
bool instack[maxn];

void init()
{
    for (int i = 0; i <= 2 * n; i++) {
        head[i] = -1;
        in[i] = dfn[i] = low[i] = 0;
    }
    vis_time = top = idx = scc = 0;
}

void tarjan(int u)
{
    int v;
    low[u] = dfn[u] = vis_time++;
    instack[u] = true;
    st[++top] = u;
    for (int id = head[u]; ~id; id = edges[id].next) {
        v = edges[id].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        scc++;
        do {
            v = st[top--];
            instack[v] = false;
            //color_num[scc]++;
            color[v] = scc;
        } while (v != u);
    }
}

int main()
{
    int v;
    while (scanf("%d", &n) != EOF) {
        init();
        range(i, 1, n)
        {
            scanf("%d", &m);
            each(j, m)
            {
                scanf("%d", &v);
                addEdge(i, v + n);
            }
        }
        range(i, 1, n)
        {
            scanf("%d", &m);
            addEdge(m + n, i);
        }
        range(i, 1, 2 * n) if (dfn[i] == 0) tarjan(i);
        range(i, 1, n)
        {
            int num = 0, c = color[i];
            for (int id = head[i]; ~id; id = edges[id].next)
                if (c == color[edges[id].to])
                    ans[num++] = edges[id].to - n;
            sort(ans, ans + num);
            printf("%d", num);
            reach(i, num) printf(" %d", ans[i]);
            puts("");
        }
    }
    return 0;
}
稳定婚姻问题

BZOJ 2140 稳定婚姻

Posted on

稳定婚姻的判定问题。

老实说,写了几题后发现稳定婚姻问题几乎都是板子题……囧……
而且我作为入门题写的那道题好歹还披了一件外套,有几道完完全全的裸题写得我是非常的空虚……

回到这道题,这道题应该算是稳定婚姻判定的裸题了。
假如我们再次无脑套模板,复杂度还是在\( O(n^2) \)左右。
我们从另一个角度来考虑。如果我可以找到一个相互出轨的夫妻,那就是不稳定的。
从而,对于一个已知的婚姻匹配,如果存在一对夫妻离婚,但不会对其他夫妻造成任何影响,那么这组婚姻匹配就是稳定的。
稳定婚姻的判定就是通过这种方式找到可以相互出轨的夫妻。

一个可行解法就是求强联通分量。对于已知匹配建立好单向二分图,对于可出轨匹配用反向边表示。然后求一下强联通分量。如果存在一组匹配,他们被染色的数量超过 \( 1 \) 是什么颜色呢??
那这个婚姻匹配就是不稳定的。
复杂度为Tarjan的复杂度,估计在\( O( n ) \) 左右。

题意:
先给你一组婚姻匹配,再给你几组可出轨匹配,问你对于每一对夫妻,他们的匹配是否安全。

思路:
裸题啦,裸题,看了我上面的陈述就知道该怎么写了。

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;

const int maxn = 8005;
const int maxm = 3e4 + 5;

int n, m;

map<string, int> man, woman;
string rman[maxn], rwoman[maxn];

int head[maxn], idx;
struct node {
    int to;
    int next;
} edges[maxm];

void addEdge(int u, int v)
{
    edges[idx] = (node){ v, head[u] };
    head[u] = idx++;
}

int scc, top, vis_time;
int dfn[maxn], low[maxn], in[maxn], color[maxn], st[maxn], color_num[maxn];
bool instack[maxn];

void init()
{
    man.clear(), woman.clear();
    for (int i = 0; i <= 2 * n; i++) {
        head[i] = -1;
        in[i] = dfn[i] = low[i] = 0;
    }
    vis_time = top = idx = scc = 0;
}

void tarjan(int u)
{
    int v;
    low[u] = dfn[u] = vis_time++;
    instack[u] = true;
    st[++top] = u;
    for (int id = head[u]; ~id; id = edges[id].next) {
        v = edges[id].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        color_num[++scc] = 0;
        do {
            v = st[top--];
            instack[v] = false;
            color_num[scc]++;
            color[v] = scc;
        } while (v != u);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    string u, v;
    while (cin >> n) {
        init();
        range(i, 1, n)
        {
            cin >> rwoman[i] >> rman[i];
            man[rman[i]] = i;
            woman[rwoman[i]] = i;
            addEdge(i + n, i);
        }
        cin >> m;
        range(i, 1, m)
        {
            cin >> u >> v;
            addEdge(woman[u], man[v]);
        }
        range(i, 1, 2 * n) if (dfn[i] == 0) tarjan(i);
        range(i, 1, n) if (color_num[color[i]] == 1) puts("Safe");
        else puts("Unsafe");
    }
    return 0;
}
稳定婚姻问题

稳定婚姻问题入门

Posted on

第一次看了理论之后自己敲代码直接 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;
}