求关键路径长度

先拓扑排序再动态规划求事件最早开始时间的最大值。
struct Edge {
int to;
int length;
Edge(int x,int y):to(x),length(y) {
}
};

vector<Edge> graph[Max];
int indegree[Max]= {0};
int el[Max]= {0};


void CritialPath(int n) {
queue<int> q;
for(int i=0; i<n; i++) {
if(indegree[i]==0) {
q.emplace(i);
el[i]=1;                                                              //事件的最早开始时间
}
}
while(!q.empty()) {
int u=q.front();
q.pop();                                                                        //删点
for(int i=0; i<graph[u].size(); i++) {                             //遍历该点所有的连接点,修改求各个事件的最早开始时间,并从下一个度为0的点开始。
int v=graph[u][i].to;
int l=graph[u][i].length;
indegree[v]--;                                                        //删边
if(indegree[v]==0) {
q.emplace(v);
}
el[v]=max(el[v],el[u]+l);                                        //动态规划,求各个事件的最早开始时间。
}
}
return ;
}
全部评论
我在牛客上刷到过路径的题
点赞 回复 分享
发布于 2022-10-15 21:02 山西

相关推荐

不愿透露姓名的神秘牛友
2025-11-19 14:56
点赞 评论 收藏
分享
2025-11-26 14:42
郑州轻工业大学 Java
在写周报的打工人很独...:这个笔试昨天晚上做了一下,真难啊,前后端,ai全有
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务