洛谷 P1407 [国家集训队]稳定婚姻 题解【tarjan】【环】

点击量：548

看上去是二分图匹配？？

目录

题目背景

我国的离婚率连续7年上升，今年的头两季，平均每天有近5000对夫妇离婚，大城市的离婚率上升最快，有研究婚姻问题的专家认为，是与简化离婚手续有关。

 

25岁的姗姗和男友谈恋爱半年就结婚，结婚不到两个月就离婚，是典型的“闪婚闪离”例子，而离婚的导火线是两个人争玩电脑游戏，丈夫一气之下，把电脑炸烂。

 

有社会工作者就表示，80后求助个案越来越多，有些是与父母过多干预有关。而根据民政部的统计，中国离婚五大城市首位是北京，其次是上海、深圳，广州和厦门，那么到底是什么原因导致我国成为离婚大国呢?有专家分析说，中国经济急速发展，加上女性越来越来越独立，另外，近年来简化离婚手续是其中一大原因。

 

——以上内容摘自第一视频门户

 

题目描述

现代生活给人们施加的压力越来越大，离婚率的不断升高已成为现代社会的一大问题。而其中有许许多多的个案是由婚姻中的“不安定因素”引起的。妻子与丈夫吵架后，心如绞痛，于是寻求前男友的安慰，进而夫妻矛盾激化，最终以离婚收场，类似上述的案例数不胜数。

 

我们已知n对夫妻的婚姻状况，称第i对夫妻的男方为Bi，女方为Gi。若某男Bi与某女Gj曾经交往过（无论是大学，高中，亦或是幼儿园阶段，i≠j），则当某方与其配偶（即Bi与Gi或Bj与Gj）感情出现问题时，他们有私奔的可能性。不妨设Bi和其配偶Gi感情不和，于是Bi和Gj旧情复燃，进而Bj因被戴绿帽而感到不爽，联系上了他的初恋情人Gk……一串串的离婚事件像多米诺骨牌一般接踵而至。若在Bi和Gi离婚的前提下，这2n个人最终依然能够结合成n对情侣，那么我们称婚姻i为不安全的，否则婚姻i就是安全的。

 

给定所需信息，你的任务是判断每对婚姻是否安全。

 

输入输出格式

输入格式：

第一行为一个正整数n，表示夫妻的对数；

 

以下n行，每行包含两个字符串，表示这n对夫妻的姓名（先女后男），由一个空格隔开；

 

第n+2行包含一个正整数m，表示曾经相互喜欢过的情侣对数；

 

以下m行，每行包含两个字符串，表示这m对相互喜欢过的情侣姓名（先女后男），由一个空格隔开。

 

输出格式：

输出文件共包含n行，第i行为“Safe”（如果婚姻i是安全的）或“Unsafe”（如果婚姻i是不安全的）。

输入输出样例

输入样例#1：

2

Melanie Ashley

Scarlett Charles

1

Scarlett Ashley

输出样例#1：

Safe

Safe

输入样例#2：

2

Melanie Ashley

Scarlett Charles

2

Scarlett Ashley

Melanie Charles

输出样例#2：

Unsafe

Unsafe

说明

对于20%的数据，n≤20；

 

对于40%的数据，n≤100，m≤400；

 

对于100%的数据，所有姓名字符串中只包含英文大小写字母，大小写敏感，长度不大于8，保证每对关系只在输入文件中出现一次，输入文件的最后m行不会出现未在之前出现过的姓名，这2n个人的姓名各不相同，1≤n≤4000，0≤m≤20000。

   首先看到这个题，会想到二分图匹配，二分图匹配有两种做法，一是匈牙利，二是网络最大流。网络最大流不够直观，而且在这个题里本来就有n对夫妻，最大流量就是n，我们考虑利用匈牙利。

   在匈牙利算法中，当一条增广路匹配成功后，就不再匹配了，这样找出的状况不够全面。如果要找出全部的状况，则需要较高的复杂度（约$ O(n^2m)$），是跑不过去的。不过我们可以利用匈牙利找增广路的方式来换一种思路。

   我们这个题中“婚姻不安全”定义为Bi出轨后，Gi也会被出轨的情况。也就是本身的夫妻边不连接，可以通过匈牙利转回自己来，也就是成环了。因此我们可以用tarjan算法求出图中的环，环上的点所代表的夫妻，婚姻关系就是不安全的。虽然题目中将夫妻关系抽象为两个点，但它们实则是一个点，因为每对夫妻都会有一条边，仅连接着这两条边。那么我们认为，此时的“婚外情”是女生连男生（男生连女生的夫妻边被合掉了），从而构建出一个图。

   我们只要在新构建的图里找出所有环，那么环上的夫妻都可能通过这个环发生不安全的婚姻，这些婚姻就是不安全的。

Code：

#include<cstdio>
#include<cstring>
#include<map>
#include<iostream>
using std::string;
using std::cin;
using std::map;
using std::min;
map<string,int> m;
struct node
{
    int n;
    node *nxt;
    node(int n)
    {
        this->n=n;
        nxt=NULL;
    }
    node()
    {
        nxt=NULL;
    }
};
node head[4010],*tail[4010];
int dfn[4010],low[4010],cnt=0;
int s[4010],top=0;
bool isaf[4010],in[4010];
//判断是否安全和是否在栈里
void tarjan(int x)
{
    dfn[x]=++cnt;
    low[x]=dfn[x];
    s[++top]=x;
    in[x]=true;
    node *p=&head[x];
    while(p->nxt!=NULL)
    {
        p=p->nxt;
        if(dfn[p->n]&&!in[p->n])//如果已经被归为其他强连通分量，就不管
            continue;
        if(dfn[p->n])
            low[x]=min(low[x],dfn[p->n]);
        else
        {
            tarjan(p->n);
            low[x]=min(low[x],low[p->n]);
        }
    }
    if(low[x]==dfn[x])
    {
        if(s[top]==x)//说明不在环上
        {
            top--;
            in[x]=false;
            return;
        }
        while(s[top]!=x)
        {
            in[s[top]]=false;
            isaf[s[top]]=false;
            top--;
        }
        in[s[top]]=false;
        isaf[s[top]]=false;
        top--;
    }
}
int main()
{
    memset(isaf,true,sizeof(isaf));
    memset(in,false,sizeof(in));
    string s1,s2;
    int n,M;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>s1>>s2;
        m[s1]=i;//判断字符串
        m[s2]=i;
        tail[i]=&head[i];
    }
    scanf("%d",&M);
    int k;
    for(int i=1;i<=M;i++)
    {
        cin>>s1>>s2;
        k=m[s1];
        tail[k]->nxt=new node(m[s2]);
        tail[k]=tail[k]->nxt;
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);

    for(int i=1;i<=n;i++)
        if(isaf[i])
            puts("Safe");
        else
            puts("Unsafe");
    return 0;
}