社区讨论

求助:这道题咋搞啊

灌水区参与者 5已保存回复 10

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
10 条
当前快照
1 份
快照标识符
@mi7xnnjl
此快照首次捕获于
2025/11/21 05:18
4 个月前
此快照最后确认于
2025/11/21 05:18
4 个月前
查看原帖
CPP
一家公司拥有 n 名雇员,编号从 1 到 n 。每名雇员要么没有直接上司,要么只有一位直接上司 (直接上司是另一名具有不同编号的雇员)。如果满足以下条件之一,那么一名雇员 A 就被称之为另一名雇员 B 的 主管:

雇员 A 是雇员 B 的直接上司;
雇员 B 的直接上司是雇员 C,而雇员 A 是雇员 C 的主管。
该公司在管理上不会形成层级循环。换言之,不会存在一名雇员是他/她自己的直接上司的主管。

今天,该公司将举办一场聚会。这涉及到将全部的 n 名雇员划分到多个小组中:每名雇员必须恰好属于一个小组。此外,在任何一个小组内,不允许存在两名雇员 A 和 B,使得 A 是 B 的主管。

请问,至少应划分多少个小组?

输入格式
第一行包含了整数 n (1 ≤ n ≤ 2000) — 雇员的数目。

接下来的 n 行包含了整数 pi (1 ≤ pi ≤ n 或 pi = -1)。每一个 pi 表示第 i 名雇员的直接上司。如果 pi 是 -1,则意味着第 i 名雇员没有直接上司。

数据保证:没有雇员会是他/她自己的直接上司 (pi ≠ i)。同时,不会出现管理层级的循环。

输出格式
打印一个唯一的整数,表示聚会中将会划分的小组的最少数目。

输入输出样例
输入
5
-1
1
2
1
-1
输出
3
样例说明
对于第一个示例,三个小组是足够的,例如:

雇员 1
雇员 24
雇员 35
我写成这个样子,但是不知道怎么统计最终答案。。。
#include<bits/stdc++.h>
using namespace std;
vector<int> v[2010];
int n,ans=0;
int dfs(int node,int far){
	int res=0; 
	for(register int i=0;i<v[node].size();i++){
		if(v[node][i]!=far){
			 int x=dfs(v[now][i],node)+1;
			 if(x>res) res=x;
		}
}
int x[2010];
int main(){
	register int n;
	scanf("%d",&n);
	for(register int i=1;i<=n;i++){
		scanf("%d",&x[i]);
		if(x[i]!=-1){
			v[i].push_back(x[i]);
			v[x[i]].push_back(i);
		}
	}
	for(register int i=1;i<=n;i++){
		scanf("%d",&x[i]);
		if(x[i]==-1) dfs(i,-1);
	}
	for(register int i=1;i<=n;i++){  
				
	}
}

回复

10 条回复,欢迎继续交流。

正在加载回复...