LC5909-并行课程III

5909. 并行课程 III

DAG上的动态规划 板子题

const int N = 5e4 + 20;
int h[N],ne[N * 2], e[N * 2],idx,res,q[N],hh,tt,n,d[N],ddl[N];
class Solution {
public:
    void add(int a, int b){e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}
    bool topsort(vector& time){
        int hh = 0, tt = -1;
        int tmp = 0;
        for (int i = 1; i <= n; i ++ )
            if (!d[i]){
                q[ ++ tt] = i;
                ddl[i] = time[i - 1];
            }
        while (hh <= tt){
            int t = q[hh ++ ];
            int tmp = 0;
            for (int i = h[t]; i != -1; i = ne[i]){
                int j = e[i];
                if (-- d[j] == 0)q[ ++ tt] = j;
                ddl[j] = max(ddl[t] + time[j - 1], ddl[j]);
            }
        }
        return tt == n - 1;
    }
    int minimumTime(int _n, vector>& relations, vector& time) {
        n = _n;
        memset(h, -1, sizeof h);
        memset(ddl, 0, sizeof ddl);
        idx = res = 0;
        for(auto& e : relations) add(e[0], e[1]), d[e[1]] ++;
        topsort(time);
        for(int i = 1; i <= n; ++i) res = max(res, ddl[i]);
        return res;
    }
};