【中】L2-016 愿天下有情人都是失散多年的兄妹 (25 分) 搜索

发布时间:2019年03月17日 阅读:276 次

L2-016 愿天下有情人都是失散多年的兄妹 (25 分)

呵呵。大家都知道五服以内不得通婚,即两个人最近的共同祖先如果在五代以内(即本人、父母、祖父母、曾祖父母、高祖父母)则不可通婚。本题就请你帮助一对有情人判断一下,他们究竟是否可以成婚?

输入格式:

输入第一行给出一个正整数N(2  N ),随后N行,每行按以下格式给出一个人的信息:

本人ID 性别 父亲ID 母亲ID

其中ID是5位数字,每人不同;性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考,则相应的ID位置上标记为-1

接下来给出一个正整数K,随后K行,每行给出一对有情人的ID,其间以空格分隔。

注意:题目保证两个人是同辈,每人只有一个性别,并且血缘关系网中没有乱伦或隔辈成婚的情况。

输出格式:

对每一对有情人,判断他们的关系是否可以通婚:如果两人是同性,输出Never Mind;如果是异性并且关系出了五服,输出Yes;如果异性关系未出五服,输出No

输入样例:

24
00001 M 01111 -1
00002 F 02222 03333
00003 M 02222 03333
00004 F 04444 03333
00005 M 04444 05555
00006 F 04444 05555
00007 F 06666 07777
00008 M 06666 07777
00009 M 00001 00002
00010 M 00003 00006
00011 F 00005 00007
00012 F 00008 08888
00013 F 00009 00011
00014 M 00010 09999
00015 M 00010 09999
00016 M 10000 00012
00017 F -1 00012
00018 F 11000 00013
00019 F 11100 00018
00020 F 00015 11110
00021 M 11100 00020
00022 M 00016 -1
00023 M 10012 00017
00024 M 00022 10013
9
00021 00024
00019 00024
00011 00012
00022 00018
00001 00004
00013 00016
00017 00015
00019 00021
00010 00011

输出样例:

Never Mind
Yes
Never Mind
No
Yes
No
Yes
No
No
#include<bits/stdc++.h>
using namespace std;
int fa[100000];
int ma[100000];
int sex[100000];
bool dfs(int a,int b,int cnt)
{

    if(a==-1||b==-1)return 1;

    if(ma[a]!=-1&&ma[a]==ma[b])return 0;
    if(fa[a]!=-1&&fa[a]==fa[b])return 0;
    cnt++;
    if(cnt>=4)
    {

        return 1;
    }
    return dfs(fa[a],fa[b],cnt)&&dfs(ma[a],fa[b],cnt)&&dfs(ma[a],ma[b],cnt)&&dfs(fa[a],ma[b],cnt);
}
int main()
{

    int n;
    cin>>n;
    memset(fa,-1,sizeof fa);
    memset(ma,-1,sizeof ma);
    for(int i=1; i<=n; i++)
    {

        int a,fa1,ma1;

        char mm[3];
        cin>>a>>mm>>fa1>>ma1;
        if(mm[0]=='M')
        {
            sex[a] = 0;

        }
        else sex[a] = 1;
        if(fa1!=-1)
        {

            sex[fa1] = 0;
            fa[a] = fa1;
        }
        if(ma1!=-1)
        {

            sex[ma1]  =1;
            ma[a] = ma1;
        }

    }
    int k;
    cin>>k;
    for(int i=1; i<=k; i++)
    {

        int aa,bb;
        cin>>aa>>bb;
        int f = dfs(aa,bb,0);
        if(sex[aa]==sex[bb])printf("Never Mind\n");
        else if(f)printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}

CODE2
#include<iostream>
#include<string.h>
#define MAX 100010
using namespace std;
int father[MAX],mother[MAX];
typedef struct Man
{
    char sex;
    int fa,mo;
};
Man man[MAX];
int Find(int a,int b,int num)
{
    if(a == -1 || b == -1)
        return 1;
    if((mother[a] != -1 && mother[a] == mother[b]) || (father[a] != -1 && father[a] == father[b]))
        return 0;
    num++;
    if(num >= 4)
        return 1;
    return (Find(mother[a],mother[b],num) && Find(mother[a],father[b],num) && Find(father[a],father[b],num) && Find(father[a],mother[b],num));
}
int main()
{
    memset(father,-1,sizeof(father));
    memset(mother,-1,sizeof(mother));
    int n,m;
    cin >> n;
    for(int i = 0;i < n; i++)
    {
        int a;
        cin >> a;
        cin >> man[a].sex >> man[a].fa >> man[a].mo;
        if(man[a].fa != -1)
        {
            father[a] = man[a].fa;
            man[man[a].fa].sex = 'M';//父母的性别没有设置,需要手动设置
        }
        if(man[a].mo != -1)
        {
            mother[a] = man[a].mo;//父母的性别没有设置,需要手动设置
            man[man[a].mo].sex = 'F';
        }
 
        if(man[a].fa == -1)
            father[a] = -1;
        if(man[a].mo == -1)
            mother[a] = -1;
    }
    cin >> m;
    for(int i = 0;i < m; i++)
    {
        int a,b;
        cin >> a >> b;
        if(man[a].sex == man[b].sex)
            cout <<"Never Mind"<<endl;
        else
        {
            int num = 0;
            if(Find(a,b,num))
                cout <<"Yes"<<endl;
            else
                cout <<"No"<<endl;
        }
    }
    return 0;
}


Tag:
相关文章

发表评论: