NC219967. 来自wzc的简单拓扑dp
描述
输入描述
第一行包含两个整数n,m（1<=n<=1e5,1<=m<=min(n*(n+1)/2,2e5))表示除了起点外的顶点的个数，以及有向边的条数。第二行为n个空格隔开的整数xi，分别代表顶点1，顶点2，.......顶点n上的数字。（1<=xi<=1000）接下来m行，每行两个整数a,b（0<=a,b<=n)，代表有一条有向边从顶点a指向顶点b。
输出描述
输出一个整数，表示wzc能得到的最大数字和是多少。
示例1
输入:
5 6 9 5 8 7 4 0 4 2 1 1 5 3 5 4 3 4 2
输出:
25
C++(clang++11) 解法, 执行用时: 282ms, 内存消耗: 14356K, 提交时间: 2021-03-30 19:37:34
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a[100002],n;
vector<ll>v[100002];
ll dp[100002];
ll dfs(int b){
if(dp[b])return dp[b];
dp[b]=a[b];
for(int i:v[b])dp[b]=max(dfs(i)+a[b],dp[b]);
return dp[b];
}
int main(){
ll n,m,x,y;cin>>n>>m;
for(int i=1;i<=n;++i)cin>>a[i];
while(m--){
cin>>x>>y;v[x].push_back(y);
}
cout<<dfs(0)<<endl;
return 0;
}