P10124 [USACO18OPEN] Family Tree B 题解

思路

这道题目很像找 \(2\) 头牛的最近公共祖先，即 lca, 但是并不用那么麻烦.

因为数据很小，我们可以写一个 山寨版 的 lca.具体如下.

int mother(string x, string y) {
	int res = 0;
	while (y != "") { // 有名字的牛
		if (x == y) return res; // 两头牛的名字相等，说明是同一头牛，返回步数
		y = find_mom(y); // y 去找它的母亲
		res++; // 步数++
	}
	return -1; // 没找到
}

先说下 find_mom 这个函数的功能.

string find_mom(string cow) {
	for (int i = 1; i <= n; i++) 
		if (cow == son[i]) return mom[i];
	return "";
} 

就是找一头牛的母亲，如果没有找到，返回空白字符串.

再讲一下 son[i] 和 mom[i].

son[i] 存储孩子，mom[i] 存储母亲.

言归正传，首先 y != "" 是要表明这头牛是在数组中的.

res 是用来存 y 到 x 的步数.所以，在这个函数中，\(x\) 是 不动的，\(y\) 是在 动 的.

因为题目中的输出是遵循 年纪老的在前，年轻牛在后，所以我们需要存储 \(2\) 个变量.

\(sx\), \(sy\)，分别表示 \(x\), \(y\) 到它们的 最近公共祖先的步数.

基本操作顺序

第一次，我们先假设 lca 为奶牛 x. 如果 lca 不为空且它和奶牛 y是有直系关系的，那么不用在找了.

否则，我们动 lca，步数存在 \(sx\) 中.

如果退出循环后 lca 为空，说明 x 和 y 没有关系.

然后我们就可以去查询 y 到 lca 的步数，即 \(sy\).

判断

如果 sx 和 sy 的值均为 1，说明它们只需要各动 1 步就到 lca 了，也就是说，它们是姐妹关系.

如果两个值均大于 1，那就是 cousin 的关系了.

这两个关系在题目中的图片就可以明白.

接下来就是 great great .... grand mother / aunt 关系了.

先根据 \(sy\) 和 \(sx\) 区分前辈和后辈.因为题目中是以 y 为后辈，所以，当 \(sy > sx\) 时，就要互换身份了.

接下来输出 \(t\) 个 great-.

\(t\) 是 \(sx - 2\) 个. 为什么? 首先 x 时后辈，并且 mother 和 grand-mother 不需要 grant，所以要减 \(2\).

然后判断要不要输出 grand.

因为只有直系关系才有 grand, 所以当 \(sx > 1\) 并且 \(sy = 0\) 时，才输出 grand.

\(sx > 1\) 是因为 mother 没有 grand, 只有mother 的 mother 及以上才有 grand.

\(sy = 0\) 是为了区分 mother 和 aunt.

然后如果 \(sy = 0\)，再输出 mother，否则就是 aunt.

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int n;
string x, y;
string lca; // 存公共祖先 
string mom[102], son[102];
int sx, sy;

string find_mom(string cow) {
	for (int i = 1; i <= n; i++) 
		if (cow == son[i]) return mom[i];
	return "";
} 

int mother(string x, string y) {
	int res = 0;
	while (y != "") {
		if (x == y) return res;
		y = find_mom(y);
		res++;
	}
	return -1;
}

int main() {
	cin >> n >> x >> y;
	for (int i = 1; i <= n; i++)
		cin >> mom[i] >> son[i];
	lca = x;
	while (lca != "") { // 没有跑出族谱 
		if (mother(lca, y) != -1) 
			break;
		lca = find_mom(lca);
		sx++;
	}
	if (lca == "") {
		printf("NOT RELATED");
		return 0;
	}
	int sy = mother(lca ,y);
	if (sx == 1 && sy == 1) printf("SIBLINGS");
	else if (sx > 1 && sy > 1) printf("COUSINS");
	else {
		if (sy > sx) 
			swap(x, y), swap(sx, sy);
		printf("%s is the ", y.c_str());
		for (int i = 1; i <= sx - 2; i++) 
			printf("great-");
		if (sx > 1 && sy == 0) printf("grand-");
		if (sy == 0) printf("mother");
		else printf("aunt");
		printf(" of %s", x.c_str());
	}
	return 0;
}