BZOJ 2140 稳定婚姻

稳定婚姻的判定问题。

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

回到这道题，这道题应该算是稳定婚姻判定的裸题了。
假如我们再次无脑套模板，复杂度还是在( 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;
}