2050 并行课程 III

原题链接

题解：拓扑排序+动态规划

我们首先根据给定的先修课程关系，构建出一个有向无环图。已知每个结点的时间都是time[i-1]+其入度结点的最大值。最后比较出最大的出度为零的结点的时间

code

class Solution {
public:
    static const int N=5e4+5;
    int head[N],Next[N],to[N],finish[N],sum[N],m,cnt=0,que[N];
    void build(int x,int y){
        Next[++cnt]=head[x];
        to[cnt]=y;
        head[x]=cnt;
        sum[y]++;
    }
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        m=relations.size();
        int l=0,r=0,ans=0;
        for (int i=0;i<m;i++){
            build(relations[i][0],relations[i][1]);
        }
        for (int i=1;i<=n;i++)
            if (sum[i]==0){
                finish[i]=time[i-1];
                que[r++]=i;
            }
        while (l<r){
            int from=que[l++];
            for (int i=head[from];i>0;i=Next[i]){
                if (finish[from]>finish[to[i]]) finish[to[i]]=finish[from];  //必须先更改再进行累加（time[i-1]的值可能比入度结点的值还要大，就起不到累加的效果）
                if (--sum[to[i]]==0){
                    que[r++]=to[i];
                    finish[to[i]]+=time[to[i]-1];
                }
            }
            if (head[from]==0) ans=finish[from]>ans ? finish[from] : ans;
        }
        return ans;
    }
};