天梯赛 愿天下有情人都是失散多年的兄妹(DFS)

2018-01-29 12:40:28来源:网络收集作者:程序诗人人点击

分享

一开始做的时候一直卡在17分,怎么看都觉得没有问题,最后看了别人博客才知道,竟然还会询问某人的父母和其他人的父母可否结婚(当然是选择原谅TA啦)。。。。像我这样纯洁的小孩子根本就考虑不到啊。。。
所以,在输入父母的序号时也需将性别标记上。


题目说要保证5代之间没有血缘关系,那么可以先找其中一人的5代并都进行标记,再找第二个人的5代,若第二个人的5代中有已经被标记的,那么说明他们不可以结婚。


此题的抽象模型类似于一颗二叉树。


#include
#include
#include
#include
#include
#include
using namespace std;
struct peo{
int id; char sex;
}peo[10011];
int fpre[10015], mpre[10015];
int vis1[10015];
bool flag = true;
void DFS(int f1,int m1,int cnt){
if(cnt >= 5) return;
if(!flag) return; // 存在血缘关系就退出
if(f1 != -1){
if(vis1[f1] == 1)
flag = false;
vis1[f1] = 1;
}
if(m1 != -1){
if(vis1[m1] == 1)
flag = false;
vis1[m1] = 1;
}
if(f1 != -1)
dfs(fpre[f1], mpre[f1],cnt+1); // 父亲的父母
if(m1 != -1)
dfs(fpre[m1], mpre[m1],cnt+1); // 母亲的父母
}
int main(){
int n; cin >> n;
memset(fpre,-1,sizeof(fpre)); memset(mpre,-1,sizeof(mpre));
for(int i = 0; i < n; ++i){
int id; char sex; int f,m;
cin >> id >> sex >> f >> m;
peo[id].id = id; peo[id].sex = sex;
fpre[id] = f; mpre[id] = m; // 父亲和母亲的序号
peo[f].id = f; peo[f].sex = 'M'; // 写入父母的信息
peo[m].id = m; peo[m].sex = 'F';
}
int ask;
cin >> ask;
while(ask--){
int id1,id2; cin >> id1 >> id2;
if(peo[id1].sex == peo[id2].sex){ // 本人也算作一代
cout <<"Never Mind" << endl; continue;
}
flag = true;
memset(vis1,0,sizeof(vis1));
int f1 = fpre[id1], m1 = mpre[id1];
int f2 = fpre[id2], m2 = mpre[id2];
dfs(f1,m1,1); // 除去本人这一代,所以从1开始
dfs(f2,m2,1);
if(flag)
cout <<"Yes" << endl;
else
cout <<"No" << endl;
}
return 0;
}

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台