拓扑之家务活

题目

思路

有点树归的感觉？？听说是拓扑（雾），可能水多了，自己写的啥都不知道了
对于一个节点u，他的每一个子节点v必须都处理完，才能处理u
Max为字节点中时间最长的
然后

return tmin[u]=Max+t[u];

没了好像

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+10;
const int z=10000+5;
int n,t[maxn],tmin[maxn],cd[maxn],rd[maxn];
vector<int>son[maxn];
int dfs(int now){
    if(cd[now]==0)return tmin[now]=t[now];
    if(tmin[now])return tmin[now];
    int Max=0;
    int len=son[now].size();
    for(int i=0;i<len;i++){
        if(tmin[son[now][i]]==0)dfs(son[now][i]);
        Max=max(Max,tmin[son[now][i]]);
    }
    return tmin[now]=Max+t[now];
}
int main(){
    scanf("%d",&n);
    for(int i=1,num;i<=n;i++){
        scanf("%d%d",&t[i],&num);
        for(int j=1,x;j<=num;j++){
            scanf("%d",&x);
            son[i].push_back(x);
            rd[x]++;
            cd[i]++;
        }
    }
    for(int i=1;i<=n;i++){
        if(rd[i]==0)son[z].push_back(i);
    }
    cd[z]++;
    int ans=dfs(z);
    printf("%dn",ans);
}