求关键路径长度
先拓扑排序再动态规划求事件最早开始时间的最大值。
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 ;
}