P1113 杂务

拓扑排序模板。求DAG上最长链。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
int d[maxn],n,dp[maxn],ans=-0x3f3f3f3f;
vector<int> e[maxn];
int dfs(int u){
    if(dp[u])return dp[u];
    for(auto v:e[u]){
        dp[u]=max(dp[u],dfs(v));
    }
    dp[u]+=d[u];
    return dp[u];
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y;cin>>y;
		cin>>d[i];
		while(1){
			cin>>x;
			if(x==0)break;
			e[x].push_back(y);//这里y改为x也可以，只是意义不同
		}
	}
	for(int i=n;i>=1;i--)ans=max(ans,dfs(i));
	cout<<ans;
	return 0;
}

P1113 杂务

原文：https://www.cnblogs.com/kkksc0100/p/other_things1.html