概念
AOV网
-
一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。
-
一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行。如图3-6是一个具有三个顶点的回路，由A -> B边可得B活动必须在A活动之后，由B -> C边可得C活动必须在B活动之后，所以推出C活动必然在A活动之后，但由C -> A边可得C活动必须在A活动之前，从而出现矛盾，使每一项活动都无法进行。这种情况若在程序中出现，则称为死锁或死循环，是应该必须避免的。
-
在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列
求解方法
- 判环，有环的DAG不可能有拓扑序列，因此本身可用来判环，也可用tarjan与深搜，这里介绍深搜.vis[i] = {0,1,-1};0表示未访问，1表示已访问，-1表示正在访问栈中，深搜时如果遇见访问栈中的点，说明有环；该点未访问但搜下去有环也返回false；
- 遍历所有点，把入度为0的点放入队列中；
- 每次从队列中取出点，放入序列记录数组，并把该点所指向的点的入度-1（即是删除该点指向其他点的边），如果被指向的点入度也变为0，放入队列，重复至队列为空。
判环
inline bool topddfs(int x) {
vis[x] = -1;
for(rint i = head[x];i;i = e[i].last) {
if(vis[e[i].to] == -1) return 0;
if(!vis[e[i].to] && !topddfs(e[i].to)) return 0;
}
vis[x] = 1;
return 1;
}
主程序
inline void topsort() {
for(rint i = 1;i <= n; ++i) {
if(in[i] == 0) q.push(i);
}
while(q.size()) {
int x = q.front();q.pop();
ans[++top] = x;
for(rint i = head[x];i;i = e[i].last) {
--in[e[i].to];
if(in[e[i].to] == 0) q.push(e[i].to);
}
}
}
求最长/短路
易得dp方程为dp[to] = max(dp[to],dp[x]);
可在每次去边的同时更新dp[]并更新pre[];
最长路每次dp[]初始为0，最短则初始为极大值；
记录路径方法
inline void gt(int x) {//递归
if(x == 0) return ;
gt(pre[x]);
ans[++top] = x;
}
while(xb) {//循环
ans[++top] = xb;
xb = pre[xb];
}//注意，两种方法得到的序列顺序不同
关键路径
概念
- 关键路径通常（但并非总是）是决定项目工期的进度活动序列。它是项目中最长的路径，即使很小浮动也可能直接影响整个项目的最早完成时间。关键路径的工期决定了整个项目的工期，任何关键路径上的终端元素的延迟在浮动时间为零或负数时将直接影响项目的预期完成时间（例如在关键路径上没有浮动时间）。但特殊情况下，如果总浮动时间大于零，则有可能不会影响项目整体进度。
- 一个项目可以有多个、并行的关键路径。另一个总工期比关键路径的总工期略少的一条并行路径被称为次关键路径。
- 用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE（Activity On Edge Network）网。在建筑学中也称为关键路线。AOE网常用于估算工程完成时间。
- 一个AOE网的关键路径可以不止一条。只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。只有在进入某一顶点的各有向边所代表的活动都已经结束，该顶点所代表的事件才能发生。表示实际工程计划的AOE网应该是无环的，并且存在唯一的入度为0的开始顶点和唯一的出度为0的完成顶点。
性质
- 求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；
- 只有缩短关键活动的工期才有可能缩短工期；3. 若一个关键活动不在所有的关键路径上，减少它并不能减少工期；
- 只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。
分析
从开始到结尾的最长总时间就是关键路径，也就是AOE上的最长路，求法同上