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

作者: wjyyy 分类: tarjan,,解题报告 发布时间: 2018-06-10 09:59

点击量:19

看上去是二分图匹配??

 

题目背景

我国的离婚率连续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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */