80分求助
  • 板块P1113 杂务
  • 楼主mmdxm
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/8/25 20:58
  • 上次更新2023/10/27 13:40:41
查看原帖
80分求助
526235
mmdxm楼主2022/8/25 20:58
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=10001;
int first[MAXN],Next[MAXN],ed[MAXN],cnt,ru[MAXN],ans,time[MAXN],v[MAXN];
queue<int> q;
void check(int s,int e){
	cnt++;
	ed[cnt]=e;
	Next[cnt]=first[s];
	first[s]=cnt;
}
void aov(){
	int i,x;
	q.push(1); 
	while(!q.empty()){
		x=q.front();
		q.pop();
		time[x]+=v[x];
		for(i=first[x];i!=0;i=Next[i]){
			int e=ed[i];
			ru[e]--;
			time[e]=max(time[e],time[x]);
			if(ru[e]==0){
				q.push(e); 
			}
		} 
	}
}
int main(){
	int n,i,j,k,s,e;
	scanf("%d",&n);
    time[1]=0;
	for(i=1;i<=n;i++){
		scanf("%d%d",&k,&v[i]);
		do{
			scanf("%d",&e);
			if(e!=0){
			check(e,i);
			ru[i]++;
		    }
		}while(e!=0);
	} 
	aov();
	for(i=1;i<=n;i++) ans=max(ans,time[i]);
	printf("%d",ans);
	return 0;
}
2022/8/25 20:58
加载中...