铜仁做网站,1688网,企业宣传ppt模板,WordPress允许用户修改评论关键路径-STL版
题目描述 给定有向图无环的边信息#xff0c;求每个顶点的最早开始时间、最迟开始时间。
输入 第一行图的顶点总数
第二行边的总数
第三行开始#xff0c;每条边的时间长度#xff0c;格式为源结点 目的结点 长度
输出 第一行#xff1a;第个顶点的最早…关键路径-STL版
题目描述 给定有向图无环的边信息求每个顶点的最早开始时间、最迟开始时间。
输入 第一行图的顶点总数
第二行边的总数
第三行开始每条边的时间长度格式为源结点 目的结点 长度
输出 第一行第个顶点的最早开始时间
第二行每个顶点的最迟开始时间
输入样例1 9 12 0 1 3 0 2 10 1 3 9 1 4 13 2 4 12 2 5 7 3 6 8 3 7 4 4 7 6 5 7 11 6 8 2 7 8 5
输出样例1 0 3 10 12 22 17 20 28 33 0 9 10 23 22 17 31 28 33
拓扑排序 关键路径
拓扑排序其实就是对有向无环图的顶点的一种排序每个顶点出现且只出现一次。 对一个AOV网进行拓扑排序的方法
从AOV网中选择一个入度为0的顶点并输出从网中删除该顶点和所有以它为起点的有向边重复1和2直到当前的AOV网为空或当前网中不存在入度为0的顶点为止
拓扑排序可以验证是否有环如果有环则无法将所有节点加入排序数组如果没环就可以拓扑排序序列不是唯一的可以根据节点序号递增或通过队列、栈来给出逆拓扑排序也可以是拓扑排序逆过来
逆拓扑排序的步骤
1、从AOV网中选择一个出度为0的顶点并输出
2、从网中删除该顶点和所有以它为终点的有向边
3、重复1和2直到当前的AOV网为空
关键路径从源点到汇点的有向路径可能有多条所有路径中具有最大路径长度的路径称为关键路径而把关键路径上的活动称为关键活动
活动ai的最早开始时间e(i)指该活动弧的起点所表示的事件的最早发生时间活动ai的最迟开始时间l(i)指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差活动ai的时间余量d(i)l(i)-e(i)表示在不增加完成整个工程所l(i)e(i)的活动ai是关键活动由关键活动组成的路径就是关键路径。
#includebits/stdc.h
using namespace std;
int main()
{int n;cinn;int line;cinline;//邻接矩阵int a[505][505] {0};//顶点入度int ind[505] {0};for(int i 0; i line; i){int v1,v2,v;cinv1v2v;a[v1][v2] v;ind[v2] ;}queueint q;//拓扑排序数组int ssort[505];for(int i 0; i n; i){if(ind[i] 0) {q.push(i);ind[i] -1;}}int cnt 0;while(!q.empty()){int now q.front();q.pop();//加入拓扑排序数组ssort[cnt] now;for(int i 0; i n; i){if(a[now][i]) ind[i]--;if(ind[i] 0){q.push(i);ind[i] -1;}}}//拓扑排序另一种实现方式 更方便// int num 0;// // while(num n)// {// for(int i 0; i n; i)// {// if(ind[i] 0) // {// ind[i] -1;// ssort[num] i;// for(int j 0; j n; j)// {// if(a[i][j]) ind[j]--;// }// }// }// }int start ssort[0];int end ssort[n-1];//最早开始时间和最晚开始时间int earliest[505] {-1}, latest[505] {99999999};earliest[start] 0;//最早开始时间根据拓扑排序顺序计算//即前一个的最早开始时间加上到该点的时间的最大值for(int i 1; i n; i){int ans 0;int index ssort[i];for(int j 0; j n; j){if(a[j][index]) ans max(ans,earliest[j] a[j][index]);}earliest[index] ans;}for(int i 0; i n; i){coutearliest[i] ;}coutendl;//最后一个点的最早开始时间和最晚开始时间相等latest[end] earliest[end];//最晚开始时间根据逆拓扑排序顺序计算//即后一个点的最晚开始时间减去到该点的时间的最小值for(int i n-2; i 0; i--){int index ssort[i];int ans 99999999;for(int j 0; j n; j){if(a[index][j]) ans min(ans,latest[j] - a[index][j]);}latest[index] ans;}for(int i 0; i n; i){coutlatest[i] ;}coutendl;return 0;
}另外可以用DFS求拓扑排序数组 祖先结点的DFS函数结束时间大于子孙结点的DFS函数结束时间利用DFS求出各顶点结束时间对于拓扑排序就是将结束时间从大到小排序。
