求关键路径长度

先拓扑排序再动态规划求事件最早开始时间的最大值。
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 山西

相关推荐

点赞 评论 收藏
分享
点赞 评论 收藏
分享
今天 13:51
门头沟学院 Java
周五投的,流程今天结束
投递地平线等公司7个岗位
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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