[Leaf] [P1407] 稳定婚姻

p1407-[国家集训队]-稳定婚姻---洛谷">P1407 [国家集训队] 稳定婚姻 - 洛谷

1. 题面梗概

中译中: 给定 $n$ 对夫妻和 $m$ 对曾经的情人关系。如果一对夫妻离婚后，两人都能在剩下的关系网中找到新的伴侣，且这种“重组”能让所有人依然都有伴侣，那么这对婚姻就是“不安全”的。求每对夫妻的婚姻安全性。

2. 逻辑推导

抛开题目本身背景不谈（绿题……

这看起来像是一个二分图匹配问题，但题目问的是“是否存在一种重组方案”。

2.1 环？

重组意味着什么？假如这里有三对夫妻 $A_1,B_1 \ A_2,B_2 \ A_3, B_3$。

$A_1,B_1$ 离婚了，那么 $A_1 \to B_2$，$B_2 \to C_1$ ，$C_2 \to A_2$。

所以，如果他们之间的关系构成了一个环，那这个环上所有人的婚姻都是不安全的。

2.2 建模

因为我们需要解决环，因此需要用到 Tarjan 缩点。既然如此，我们就要考虑如何建图了。

每个人之间的关系好复杂啊，如果直接连无向边呢？不行，因为 Tarjan 只能处理有向图。

接着想，男肯定不能连男，女也不能连女。那我们在建图的时候男女分开不就好了：对于每对夫妻 $G, B$，连边 $G \to B$，对于每对 情人 $G, B$，连边 $B \to G$。

如果某一对 $G, B$ 属于同一个强联通分量，说明他们不安全。

2.3 映射

由于题目给的是字符串名字，所以我们可以用 map< string, int > id 来将字符串映射成数字ID，方便图论处理。

2.4 结论

这是个 SCC 问题，也是个考验建模的好问题。

3. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 8000 + 50;
const int maxm = 20000 + 50;

map< string, int > id;
vector< int > adj[maxn];
vector< pair< int, int > > couples;
stack< int > st;

int dfn[maxn], low[maxn], timer;
bool in_stack[maxn];
int scc[maxn], scc_cnt;

string boy, girl;
int n, m;

void tarjan( int u )
{
    dfn[u] = low[u] = ++ timer;
    st.push( u );
    in_stack[u] = true;

    for( int v : adj[u] )
    {
        if( !dfn[v] )
        {
            tarjan( v );
            low[u] = min( low[u], low[v] );
        }
        else if( in_stack[v] )
        {
            low[u] = min( low[u], dfn[v] );
        }
    }

    if( dfn[u] == low[u] )
    {
        scc_cnt ++;
        int v;
        do {
            v = st.top( ); st.pop( );
            in_stack[v] = false;
            scc[v] = scc_cnt;
        } while( v != u );
    }
}

void solve( )
{
    cin >> n;

    for( int i = 1; i <= n; ++ i )
    {
        cin >> girl >> boy;
        id[girl] = i;
        id[boy] = i + n;
        couples.push_back({ i, i + n });
        adj[i].push_back( i + n );
    }
    cin >> m;
    for( int i = 1; i <= m; ++ i )
    {
        cin >> girl >> boy;
        int u = id[girl], v = id[boy];
        adj[v].push_back( u );
    }

    for( int i = 1; i <= n * 2; ++ i )
    {
        if( !dfn[i] ) tarjan( i );
    }

    for( int i = 0; i < n; ++ i )
    {
        auto [u, v] = couples[i];
        if( scc[u] == scc[v] ) cout << "Unsafe" << '\n';
        else cout << "Safe" << '\n';
    }
}

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve( );
    return 0;
}

4. 复盘

• 复杂度分析：建模：$O( (n+m) \log (names) )$，瓶颈在于 map 映射。Tarjan：$O( n+m )$，线性扫描。

• 碎碎念：现实中如果有情敌关系连成了环，那确实挺 Unsafe 的（这不好笑）。名字映射时一定要注意 $n$ 的偏移，数组记的开两倍，我就是忘了翻倍WA了好多次。

• 关联笔记：SCC 缩点