社区讨论
求助:这道题咋搞啊
灌水区参与者 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
雇员 2 和 4
雇员 3 和 5
我写成这个样子,但是不知道怎么统计最终答案。。。
#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 条回复,欢迎继续交流。
正在加载回复...