AOE知识点

求 ve[ ] 数组  时间发生的最早时间，和拓扑序列

stack<int> topOrder;
bool topologicalSort(){
	queue<int> q;
	for(int i = 0; i < n; i ++){
		if(inDegree[i] == 0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int u = q.front();
		q.pop();
		topOrder.push(u);	// 加入拓扑序列 
		for(int i = 0; i < G[u].size(); i ++){
			int v = G[u][i].v;
			inDegree[v] --;
			if(inDegree[v] == 0){
				q.push(v);
			}
			if(ve[u] + G[u][i].w > ve[v]){
				ve[v] = ve[u] + G[u][i].w;
			}
		}
	}
	if(topOrder.size() == n) return true;
	else return false; 
}

求 vl [ ] 数组

fill(vl, vl + n, ve[n - 1]);

while(!topOrder.empty()){
	int u = topOrder.top();
	topOrder.pop();
	for(int i = 0; i < G[u].size(); i++){
		int v = G[u][i].v;
		if(vl[v] - G[u][i].w < vl[u]){
			vl[u] = vl[v] - G[u][i].w;
		}
	}
} 

开始计算 e 和 l 数组。

e[ i -> j ] == L[ i -> j ] 就是关键路径

int VriticalPath(){
	memset(ve, 0, sizeof(ve));
	if(topologicalSort() == false){
		return -1;
	}
	fill(vl, vl + n, ve[n - 1]);

	while(!topOrder.empty()){
		int u = topOrder.top();
		topOrder.pop();
		for(int i = 0; i < G[u].size(); i++){
			int v = G[u][i].v;
			if(vl[v] - G[u][i].w < vl[u]){
				vl[u] = vl[v] - G[u][i].w;
			}
		}
	} 
	
	for(int u = 0; u < n; u++){
		for(int i = 0; i < G[u].size(); i++){
			int v = G[u][i].v;
			int w = G[u][i].w;
			int e = ve[u];
			int l = vl[v] - w;
			if(e == l){
				printf("%d->%d\n", u, v); 
			}		
		}
	}
	return ve[n - 1];
}

如果想把e 和 l 存起来可以用一个结构体中  加上即可。

如果事先不知道汇点编号，直接就去找ve数组的最大值即可。就是最长路径的时间。