C++14(g++5.4) 解法, 执行用时: 217ms, 内存消耗: 196560K, 提交时间: 2019-12-30 11:49:05

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e3+5;
vector<int> G[N];
int n,m,s,val[N],cost[N],in[N];
ll f[N][N];
void dfs(int u,int fa) {
	for(int i=s;i>=cost[u];i--) {
		f[u][i]=f[u][i-cost[u]]+val[u];
	}
	for(int i=0;i<cost[u];i++) f[u][i]=-1e18;
    for(int i=0;i<G[u].size();i++) {
        int v=G[u][i];
        if(v==fa) continue;
        for(int j=0;j<=s;j++) f[v][j]=f[u][j];
    	dfs(v,u);
        for(int j=0;j<=s;j++) f[u][j]=max(f[u][j],f[v][j]);
    }  
}
int main() {
    scanf("%d%d%d",&n,&s,&m);
    for(int i=1;i<=n;i++) scanf("%d",&val[i]);
    for(int i=1;i<=n;i++) scanf("%d",&cost[i]);
    for(int i=0,u,v;i<m;i++) {
        scanf("%d%d",&u,&v);
        G[v].push_back(u);
        in[u]++;
    }
    for(int i=1;i<=n;i++) {
    	if(!in[i]) G[0].push_back(i);
    }
    dfs(0,-1);
    ll ans=0;
    for(int i=0;i<=s;i++) {
        ans=max(ans,f[0][i]);
    }
    printf("%lld\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 38ms, 内存消耗: 47340K, 提交时间: 2019-12-29 22:56:15

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e3+10;
vector<int> mp[N];
ll dp[N][N],val[N],cost[N];
int indeg[N],n,s,m,x,y;
void dfs(int x,int sum){sum+=cost[x];
    for(int y:mp[x]){for(int i=sum+cost[y];i<=s;++i)dp[y][i]=dp[x][i-cost[y]]+val[y];dfs(y,sum);
        for(int i=sum+cost[y];i<=s;++i)dp[x][i]=max(dp[x][i],dp[y][i]);}
}
int main(){
    scanf("%d%d%d",&n,&s,&m);
    for(int i=1;i<=n;++i)scanf("%lld",val+i);
    for(int i=1;i<=n;++i)scanf("%lld",cost+i);
    while(m--){scanf("%d%d",&x,&y);mp[y].push_back(x);++indeg[x];}
    for(int i=1;i<=n;++i)if(!indeg[i])mp[0].push_back(i);
    dfs(0,0);printf("%lld",dp[0][s]);
    return 0;
}