关键路径

AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称AOE网。AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为终点（或汇点）。

AOE网的性质：

⑴ 只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；

⑵ 只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。

关键路径：在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。

关键活动：关键路径上的活动称为关键活动。关键活动：e[i]=l[i]的活动

　　由于AOE网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度。关键路径长度是整个工程所需的最短工期。

与关键活动有关的量：

⑴ 事件的最早发生时间ve[k]

　　ve[k]是指从始点开始到顶点vk的最大路径长度。这个长度决定了所有从顶点vk发出的活动能够开工的最早时间。

⑵ 事件的最迟发生时间vl[k]

　　vl[k]是指在不推迟整个工期的前提下,事件vk允许的最晚发生时间。

⑶ 活动的最早开始时间e[i]

　　若活动ai是由弧<vk , vj>表示，则活动ai的最早开始时间应等于事件vk的最早发生时间。因此，有：e[i]=ve[k]

⑷ 活动的最晚开始时间l[i]

　　活动ai的最晚开始时间是指，在不推迟整个工期的前提下， ai必须开始的最晚时间。若ai由弧<vk，vj>表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。因此，有：l[i]=vl[j]-len<vk, vj>

示例：

所以：

//关键路径，不是有向无环图返回-1，否则返回关键路径长度//拓扑序列stack<int> topOrder;//拓扑排序，顺便求ve数组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);//将u加入拓扑序列		for (int i = 0; i < G[u].size(); i++)		{			int v = G[u][i].v;//u的i号后继结点编号为v			inDegree[v]--;			if (inDegree[v] == 0)			{				q.push(v);			}			//用ve[u]来更新u的所有后继结点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;}//关键路径，不是有向无环图返回-1，否则返回关键路径长度int CriticalPath(){	memset(ve, 0, sizeof(ve));//ve数组初始化	if (topologicalSort() == false)	{		return -1;//不是有向无环图，返回-1	}	fill(vl, vl + n, ve[n - 1]);//vl数组初始化，初始值为汇点的ve值	//直接使用topOrder出栈即为逆拓扑序列，求解vl数组	while (!topOrder.empty())	{		int u = topOrder.top();//栈顶元素为u		topOrder.pop();		for (int i = 0; i < G[u].size(); i++)		{			int v = G[u][i].v;//u的后继结点			//用u的所有后继结点v的vl值来更新vl[u]			if (vl[v] - G[u][i].w < vl[u])			{				vl[u] = vl[v] - G[u][i].w;			}		}	}	//遍历邻接表的所有边，计算活动的最早开始时间e和最迟开始时间l	for (int u = 0; u < n; u++)	{		for (int i = 0; i < G[u].size(); i++)		{			int v = G[u][i].v, w = G[u][i].w;			//活动的最早开始时间e和最迟开始时间l			int e = ve[u], l = vl[v] - w;			//如果e==l,说明u->v是关键活动			if (e == l)			{				PRintf("%d->%d/n", u, v);//输出关键活动			}		}	}	return ve[n - 1];//返回关键路径长度}/*若事先不知道汇点编号，可以取ve数组的最大值：int maxLength = 0;for(int i=0;i<n;i++){	if(ve[i]>maxLength)	{		maxLength = ve[i];	}}fill(vl,vl+n,maxLength);若有多条关键路径，可以类比最短路径中保存前驱结点的做法，新建一个邻接表来保存所有的关键活动*/