5909. 并行课程 III

就是一个拓扑+dp

每次选没有入度的节点时dp一下

dp[i]表示完成第i个节点需要的时间

则dp[i] = max(前驱节点的dp)

class Solution {
public:
    vector<int> child[50010]; 
    vector<int> parent[50010];
    int in[50010];
    int vis[50010];
    int n;
    int dp[50010];
    void bfs(vector<int>& time)
    {
        memset(vis, 0, sizeof(vis));
        int max_v = -1;
        queue<int> Q;
        n = time.size();
        for(int i = 1; i <= n; i++)
        {
            if(in[i] == 0)
            {
                Q.push(i), max_v = max(max_v, time[i - 1]);
                dp[i] = time[i - 1];
                vis[i] = 1;
            }        
        }
        while(!Q.empty())
        {
            int u = Q.front(); Q.pop();
            int len1 = child[u].size(), len2;
            for(int i = 0; i < len1; i++)
            {
                int v = child[u][i];
                in[v]--;
                if(in[v] == 0 && vis[v] == 0)
                {
                    len2 = parent[v].size();
                    max_v = -1;
                    for(int j = 0; j < len2; j++)
                        max_v = max(max_v, dp[parent[v][j]]);
                    dp[v] = max_v + time[v - 1];
                    Q.push(v);
                }
            }
        }
        
        
    }
    
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        int len1 = relations.size();
        memset(in, 0, sizeof(in));
        n = time.size();
        for(int i = 0; i < len1; i++)
        {
            child[relations[i][0]].push_back(relations[i][1]), in[relations[i][1]]++;
            parent[relations[i][1]].push_back(relations[i][0]);
        }
        bfs(time);
        int max_ret = -1;
        for(int i = 1; i <= n; i++)
            max_ret = max(max_ret, dp[i]);
        return max_ret;
        
        
    }
};