2023.7.28 并行课程III

根据题目要求，可以分析出，需要按照拓扑序上完所有的课。每次上课都需要一定时间，可以同时上任意多门课，要求最少得时间。
比如说示例1中的一个拓扑序是123，可以让12并行，因此只需要3+5=8个时间。

可以先用拓扑排序，得出拓扑序，然后进行dp（满足拓扑序即可dp）。dp时，对每个节点，令其花费时间为自身时间+前驱结点里的最大时间（最大程度的并行）。最终答案即为f[n]。

class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) 
    {
        vector<vector<int>> g(n + 1);
        vector<vector<int>> rg(n + 1);
        vector<int> d(n + 1); //入度
        for (auto edge : relations)
        {
            int u = edge[0], v = edge[1];
            g[u].push_back(v); //建反图
            rg[v].push_back(u);
            ++d[v];
        }

        queue<int> q;
        for (int i = 1; i <= n; ++i)
            if (d[i] == 0)
                q.push(i);
        
        vector<int> path;
        while (!q.empty())
        {
            auto t = q.front(); q.pop();
            path.push_back(t);
            for (auto x : g[t])
                if (--d[x] == 0)
                    q.push(x);
        }
        vector<int> f(n + 1, 0);
        for (int i = 0; i < path.size(); ++i)
        {
            int now = path[i];
            for (auto pre : rg[now])
                f[now] = max(f[now], f[pre]);
            f[now] += time[now - 1];
        }

        return *max_element(f.begin(), f.end());
    }
};