电商设计公司,怎样做网站seo优化,企业做网站有哪些好处,个人建站免费服务器呵呵。大家都知道五服以内不得通婚#xff0c;即两个人最近的共同祖先如果在五代以内#xff08;即本人、父母、祖父母、曾祖父母、高祖父母#xff09;则不可通婚。本题就请你帮助一对有情人判断一下#xff0c;他们究竟是否可以成婚#xff1f; 输入格式#xff1a; 输… 呵呵。大家都知道五服以内不得通婚即两个人最近的共同祖先如果在五代以内即本人、父母、祖父母、曾祖父母、高祖父母则不可通婚。本题就请你帮助一对有情人判断一下他们究竟是否可以成婚 输入格式 输入第一行给出一个正整数N2 N 104随后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 题解要求五服以内不得通婚那么判断两个异性是否在五服以内只需要将他们各自五服以内的亲人找出来然后判断是否有重复就好了用bfs来寻找五服
当depth 4的时候直接结束循环就好了。判断重复的方法可以是两次bfs然后把得到的5服放入set里面看有没有重复。当然还有更快的方法就是我们先dfs第一个人的五服在depth数组里给他的五服以内亲人打上标记然后dfs第二个人在dfs的过程中如果遇到亲人在depth已经被打上标记了那么说明他俩是近亲结婚输出No否则输出Yes
思路很简单但是这个题目有坑就是当要询问的两个有情人是某个人的父母而不是单独给出的时候那么用上述算法将得到错误的答案因此为我们在读入N个人的信息的时候需要特殊处理一下即当某个人的父母没有单独给出的时候我们把f[父] m[父] -1f[母] m[母] -1经过这个处理以后可以经过所有数据
#include iostream
#include cstring
#include vector
#include cstdio
#include queue
using namespace std;
const int MAXN 100005;
int ext[MAXN];
int sex[MAXN],f[MAXN],m[MAXN];
int N;
int depth[MAXN];
int main()
{scanf(%d,N);for(int i 0;i N;i){int idf,idm,idi;char s;scanf(%d %c %d%d,idi,s,idf,idm);ext[idi] 1;//idi是单独给出的标志sex[idi] s F?1:0;f[idi] idf;if(idf ! -1) {sex[idf] 0;if(!ext[idf]) m[idf] f[idf] -1;//若父亲没有被单独的给出那么要默认设置父亲的父母为-1}m[idi] idm;if(idm ! -1) {sex[idm] 1; if(!ext[idm]) m[idm] f[idm] -1;}} int Q;scanf(%d,Q);while(Q--){int a,b;scanf(%d%d,a,b);if(sex[a] sex[b]){puts(Never Mind);continue;}else if(f[a] b || m[a] b || f[b] a || m[b] a){puts(No);continue;} else{memset(depth,0,sizeof(depth));queueint q;q.push(a);while(!q.empty()){int v q.front();q.pop();if(depth[v] 4) break; //这样五服内最高亲属下标就是4 if(m[v] ! -1) {depth[m[v]] depth[v] 1;if(ext[m[v]]) q.push(m[v]);}if(f[v] ! -1){depth[f[v]] depth[v] 1;if(ext[f[v]]) q.push(f[v]);} }while(!q.empty()) q.pop();q.push(b);int flag 1;while(!q.empty()){int v q.front();q.pop();if(depth[v] 4) break; if(depth[m[v]] || depth[f[v]]){flag 0;break;}else{if(m[v] ! -1) {depth[m[v]] depth[v] 1;if(ext[m[v]]) q.push(m[v]);}if(f[v] ! -1){depth[f[v]] depth[v] 1;if(ext[f[v]]) q.push(f[v]);} }}if(flag) puts(Yes);else puts(No);}}
}
/*
3
1 M -1 -1
2 F 3 -1
4 M 3 -11
1 M 2 3
1
2 3
*/。
