文章目录
- 题目描述
- 测试用例
- 思路分析
- 原创代码
题目描述
说明： AOE 网络是有向无环加权图，其中顶点表示事件，弧表示活动，权表示活动持续的时间，通常可以用来估算工程完成的时间，即图中从开始点到结束点之间最长的路径对应的时间。请完成一个程序，完成下列任务：
1 、计算 AOE 网络对应的拓扑排序。如果排序结果不唯一，请输出按照从小到大的顺序排列的结果。从小到大的顺序就是输入的节点序列顺序（参见下面关于输入格式的说明）。如图1中满足要求的拓扑排序是： a-b-c-d-e-f-g-h-k ,图2中满足要求的拓扑排序是：v1-v3-v5-v2-v6-v4-v7-v8-v9
2 、计算 AOE 网络的关键路径。注意关键路径可能不唯一，要求输出所有的关键路径。同样，按照是按照从小到大的顺序输出。例，如果得到两条关键路径，分别是0-1-3-6-8-9和0-1-3-4-5-8-9，那么先输出后一条路径，因为两条路径中前三个节点相同，而后一条路径第四个节点的编号小。
测试用例的输入输出格式说明：
输入：
节点的个数，边的条数；
各个节点的名称序列
边： < 起点 , 终点 , 权值 > 。说明起点和终点是在各个点在输入序列中的位置，如图1中边 <a,b> 表示为 <0,1,6> 。
输出：
拓扑排序；
关键路径
[图1][图2]（我懒得上传了）
测试用例0是与图1相对应的，测试用例1是与图2相对应的。
测试用例
输入 #1
9,11 a,b,c,d,e,f,g,h,k <0,1,6>,<0,2,4>,<0,3,5>,<1,4,1>,<2,4,1>,<4,6,8>,<4,7,7>,<3,5,2>,<5,7,4>,<6,8,2>,<7,8,4>输出 #1
a-b-c-d-e-f-g-h-k a-b-e-h-k输入 #2
9,11 v1,v2,v3,v4,v5,v6,v7,v8,v9 <0,4,6>,<0,2,4>,<0,5,5>,<4,1,1>,<2,1,1>,<1,6,8>,<1,7,7>,<5,3,2>,<3,7,4>,<6,8,2>,<7,8,4>输出 #2
v1-v3-v5-v2-v6-v4-v7-v8-v9 v1-v5-v2-v8-v9输入 #3
4,4 A,B,C,D <0,1,2>,<1,3,3>,<3,2,5>,<2,1,1>输出 #3
NO TOPOLOGICAL PATH思路分析
先说拓扑序列：
- 【一句话总结】找到度为0的所有顶点，放入队列，然后开始循环：“取队首u加入拓扑序列，出队，将u的所有后继结点的入度减1，若某个后继结点的入度变为0，则加入队列。循环终止条件是队列为空。”。
- 注意事项：由于题目要求拓扑序列是“从小到大的顺序”，所以上述“队列”我采用了优先队列——priority_queue<int, vector, greater> minHeap;
- 判断拓扑序列是否存在：应该设置cnt变量，每入队一次，就cnt++。如果循环结束后cnt != n，说明有环，拓扑序列不存在。
再说关键路径：
- 【一句话总结】求每个顶点的最早发生时间ve和最迟发生时间vl，据此求各活动的最早发生时间ae和al，若ae == al则是关键活动，加入关键图。最后dfs遍历关键图即可得到关键路径。
- 具体细节：先计算每个顶点i的“最早发生时间ve[i]”和“最迟发生时间vl[i]”。ve[]先全部初始化为0，然后按拓扑序列正序求每个顶点j的ve，公式为ve[j] = max{ve[i] + val(i, j)}，i为顶点j的任意前驱（为方便找前驱，应设一个入边邻接表）。求完ve后再求vl，vl[]先全部初始化为ve[n]（不延迟工期）。然后按拓扑序列逆序求每个顶点i的vl，公式为vl[i] = min{vl[j] - val(i, j)}，j为i的任意后继（为此要设出边表）。求了ve,vl后，再遍历所有的边（活动），求出活动(u, v)的最早开始时间ae和最迟开始时间al，若ae = al则说明是关键活动，加入关键图vector<vector<pair<int, int>>> key_adj(n)（出边型）。对于活动(u,v),公式为ae = ve, al = vl - val(u, v)。求出关键图后用dfs遍历即可得到关键路径。由于dfs需要源点参数，所以前面构建关键图的时候应该顺便统计各个顶点的入度。
原创代码
#include<stdio.h>#include<iostream>#include<vector>#include<string>#include<queue>#include<unordered_map>#include<algorithm>usingnamespacestd;voiddfs(vector<vector<pair<int,int>>>&key_adj,intstart,vector<int>&path,vector<string>&id_to_name);intmain(){intn,m;scanf("%d,%d",&n,&m);getchar();//吃换行符unordered_map<string,int>name_to_id;//顶点名称->idvector<string>id_to_name(n);//读取顶点名称for(inti=0;i<n;i++){while(1){chartmp=getchar();if(tmp!=','&&tmp!='\n'){id_to_name[i].push_back(tmp);}else{//读到逗号或换行符break;}}string s=id_to_name[i];name_to_id[s]=i;}if(n==1&&m==0){cout<<id_to_name[0]<<endl<<id_to_name[0]<<endl;return0;}//读取边vector<vector<pair<int,int>>>outEdge_adj(n);//出边邻接表(n条链组成vector,每个链本身又是vector,且元素类型是pair<int,int>)vector<vector<pair<int,int>>>inEdge_adj(n);//入边邻接表vector<int>inDegree(n,0);for(inti=0;i<m;i++){intu,v,val;scanf("<%d,%d,%d>",&u,&v,&val);getchar();//吃掉逗号或换行符outEdge_adj[u].push_back({v,val});inEdge_adj[v].push_back({u,val});inDegree[v]++;}//求拓扑序列vector<int>result;//存储最终结果（顶点下标）priority_queue<int,vector<int>,greater<int>>minHeap;//暂存入度为0的顶点for(inti=0;i<inDegree.size();i++){if(inDegree[i]==0){minHeap.push(i);}}intcnt=0;while(!minHeap.empty()){intu=minHeap.top();minHeap.pop();result.push_back(u);//加入拓扑序列cnt++;vector<pair<int,int>>vec=outEdge_adj[u];//获取顶点u的“出边链”for(inti=0;i<vec.size();i++){intv=vec[i].first;inDegree[v]--;if(inDegree[v]==0){minHeap.push(v);}}}if(cnt!=n){printf("NO TOPOLOGICAL PATH\n");return0;}for(inti=0;i<result.size();i++){intvex_id=result[i];cout<<id_to_name[vex_id];if(i!=result.size()-1){//非最后一个顶点printf("-");}else{printf("\n");}}//求关键路径vector<int>ve(n,0);//ve[i]表示顶点i的最早发生时间for(inti=0;i<result.size();i++){intu=result[i];//求顶点u的最早发生时间//遍历u的所有前驱结点vector<pair<int,int>>in=inEdge_adj[u];//in保存了u的“前驱结点+权值”intmax=0;for(intj=0;j<in.size();j++){intv=in[j].first;//v是u的前驱结点intval=in[j].second;if(ve[v]+val>max)max=ve[v]+val;}ve[u]=max;}intlast=result.back();//获取topo的最后一个顶点vector<int>vl(n,ve[last]);//vl[i]表示顶点i的最迟发生时间for(inti=result.size()-1;i>=0;i--){intu=result[i];//遍历u的所有后继结点vector<pair<int,int>>out=outEdge_adj[u];//out保存了u的“后继结点+权值”intmin=ve[last];for(intj=0;j<out.size();j++){intv=out[j].first;//v是u的后继结点intval=out[j].second;if(vl[v]-val<min)min=vl[v]-val;}vl[u]=min;}//遍历所有边，找关键活动，构建关键图vector<vector<pair<int,int>>>key_adj(n);//关键图vector<int>key_inDegree(n,0);//记录关键图中顶点的入度（后面用来找源点）for(intu=0;u<outEdge_adj.size();u++){vector<pair<int,int>>&tmp=outEdge_adj[u];for(intj=0;j<tmp.size();j++){intv=tmp[j].first;intval=tmp[j].second;//判断边(u, v)是否为关键活动intae=ve[u];//(u, v)的最早开始时间是ve[u]intal=vl[v]-val;//(u, v)的最迟开始时间是vl[u] - valif(ae==al){key_adj[u].push_back({v,val});key_inDegree[v]++;}}}//对关键图的每个链中的pair，按照first升序排序for(vector<pair<int,int>>&list:key_adj){sort(list.begin(),list.end(),[](constpair<int,int>&a,constpair<int,int>&b){returna.first<b.first;});}//找关键图源点vector<int>source;for(inti=0;i<n;i++){if(key_inDegree[i]==0&&!key_adj[i].empty()){//入度为0且在关键图中有出边，为源点source.push_back(i);}}//遍历关键图,得关键路径for(intstart:source){vector<int>path;dfs(key_adj,start,path,id_to_name);}return0;}voiddfs(vector<vector<pair<int,int>>>&key_adj,intstart,vector<int>&path,vector<string>&id_to_name){path.push_back(start);if(key_adj[start].empty()){//start无出边，是汇点for(inti=0;i<path.size();i++){intid=path[i];cout<<id_to_name[id];if(i!=path.size()-1){printf("-");}else{printf("\n");}}path.pop_back();return;}vector<pair<int,int>>tmp=key_adj[start];for(pair<int,int>i:tmp){//遍历start的后继结点intsuccessor=i.first;dfs(key_adj,successor,path,id_to_name);}path.pop_back();}
