C++图论基础题DP

Question

洛谷原题：https://www.luogu.com.cn/problem/P1113
图论，我的思路是用vector[]存图，vector[i]表示序号为i的任务，vector[i][0]表示第i的任务所需的时间，vector[i][j]（j从2开始）表示第i的任务的前驱任务
然后遍历vecotr[i][2~...]记录最大值前驱任务下标，最后用累加（sum[i]记录完成第i个任务所需的时间）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int n,a,b,sum[10005];
vector<int>c[10005];

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        c[a].push_back(b);
        while(cin>>b&&b){
        c[a].push_back(b);
        }
    }
    sum[1]=c[1][0];
    for(int i=2;i<=n;i++){
        int ans=i-1;
        for(int j=1;j<c[i].size()-1;j++)ans=max(ans,c[i][j]);
        sum[i]=sum[ans]+c[i][0];
    }
    cout<<sum[n];
    return 0;
} 

Answer 1

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 10010;
int f[N];
int time1[N];
vector<int> a[N];
int dfs(int x) {
    if (f[x]) return f[x];//该节点已经遍历过了，减枝
    for (int i = 0; i < a[x].size(); i++) {
        f[x] = max(f[x], dfs(a[x][i])); //说有子集中最大的节点
    }
    f[x] += time1[x]; // 加上自己需要的时间
    return f[x];
}
int main() {
    
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y,z;
        cin >> x >> y >> z;
        time1[x] = y;
        while(z != 0){
            a[z].push_back(x);// 只有完成z 后才能完成 x 所以有z -> x的边
            scanf("%d", &z);
        }
    }
 
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, dfs(i));
    }
    cout << ans<<endl;
    return 0;
}