链接：
关键活动
思路：
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;}
，而更像是听见了天地间冥冥中的呼唤，
