Menu
Article ACM

POJ 1904 King's Quest

NodeKey

NodeKey

• 3 min read

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

这道题或许可能是我这辈子做的最后一道稳定婚姻问题……因为本来出的就少，感觉都是套路……
求稳定婚姻就是模拟的板子，判定和所有出轨匹配就是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;
}
Share