PAT 关键活动 拓扑排序-关键路径
链接:
思路:
1、首先通过队列加邻接表完成拓扑排序:
所有入度为0的节点a入队
在邻接表中找到a的所有后继节点
后继节点入度-1
如果后继节点入度为0
则后继节点入队
2、当图中出现环时则任务调度不可行:
只要判断是否入队n次即可
3、在拓扑排序的过程中用path数组保存所有(关键活动)的前驱节点
最后通过队列和path数组
从最终活动依次往前遍历 保存出现的所有边
排序输出即可
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<algorithm> using namespace std; struct node{ int to; int w; }; struct A{ //构建结构体保存关键路径的所有边 方便排序 int a,b; }edge[4999]; vector<node>w[105]; //邻接表 vector<int>path[105]; //保存每个点关键活动的所有前驱节点 int last[105]; //保存最晚完成的时间 int degree[105]; //保存每个点的入度 int n; int cmp(A aa,A bb){ return aa.a<bb.a; } void print(int loc) //通过队列保存关键路径的所有边 { int s=0; queue<int>qq; int vis[105],head,i; memset(vis,0,sizeof(vis)); qq.push(loc); while(!qq.empty()){ head=qq.front(); qq.pop(); for(i=path[head].size()-1;i>=0;i--){ loc=path[head][i]; edge[s].a=loc; edge[s++].b=head; if(!vis[loc]){ vis[loc]=1; qq.push(loc); } } } sort(edge,edge+s,cmp); for(int i=0;i<s;i++) cout<<edge[i].a<<"->"<<edge[i].b<<endl; } void top_sort() //队列实现拓扑排序 { int i,head,loc,s=0,ans=0,ans_loc; queue<int>q; for(i=1; i<=n; i++) if(degree[i]==0) q.push(i); while(!q.empty()) { head=q.front(); s++; //n个节点全部入队才完成拓扑排序 否则构成环 ans=last[head]; ans_loc=head; //最后进队的是最终的活动 q.pop(); for(i=0; i<w[head].size(); i++) { loc=w[head][i].to; if(last[head]+w[head][i].w>last[loc]) //如果这条路径花费时间更长 { path[loc].clear(); //之前保存的前驱关键活动清空 last[loc]=last[head]+w[head][i].w; path[loc].push_back(head); //添加当前的前驱关键活动 } else if(last[head]+w[head][i].w==last[loc]) { path[loc].push_back(head); //花费时间相同-添加 } degree[loc]--; if(!degree[loc]) q.push(loc); } } if(s==n) cout<<ans<<endl; else { cout<<0<<endl; return; } print(ans_loc); //从最后的关键活动开始找出所有边 return; } int main() { int m,i,j; int a,b,weight; scanf("%d%d",&n,&m); for(i=1; i<=n; i++){ degree[i]=0; last[i]=0; } while(m--) { scanf("%d%d%d",&a,&b,&weight); w[a].push_back((node){b,weight}); degree[b]++; } top_sort(); return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。