版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41603898/article/details/101923858
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 100000000;
int head[maxn];
int cnt;
int val[20005],in[20005];
bool book[20005];
int ans[20005];
int n,as;
struct N{
int v,nxt;
}edge[maxn];
void add(int u,int v){
cnt++;
edge[cnt].v = v;
edge[cnt].nxt = head[u];
head[u] = cnt;
}
queue<int> q;
void topo(){
int v;
while(!q.empty()){
int top = q.front();
q.pop(); book[top] = false;
for(int i = head[top];i;i = edge[i].nxt){
v = edge[i].v;
in[v]--;
ans[v] = max(ans[v],val[v]+ans[top]);
as = max(as,ans[v]);
if(in[v]==0&&(!book[v])){
q.push(v); book[v] = true;
}
}
}
}
int main()
{
int id,w,last;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d %d",&id,&w);
val[id] = w;
while(scanf("%d",&last)&&last){
add(last,id);
in[id]++;
}
}
for(int i=1;i<=n;i++){
if(!in[i])q.push(i),book[i]=true;
ans[i] = val[i];
}
topo();
printf("%d\n",as);
return 0;
}