本文共 1634 字，大约阅读时间需要 5 分钟。

题目

答案

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;struct Node{   	int node,time;	Node(int a,int b):node(a),time(b){   	}};//后继节点 struct S{   	int x,y,cnt;	S(int a,int b,int c):x(a),y(b),cnt(c){   	}	bool operator <(const S &a)const{   		if(x!=a.x) return x
       
        a.cnt;	}//自定义排序方式，对应题目中的要求——任务开始的交接点编号小者优先，起点编号相同时，与输入时任务的顺序相反 };//set的存放格式 vector
        
          vec[1005];//储存下一个相连节点（可能是多个） set
          sets;//储存最终的关键活动 queue
          
            q;//按照拓扑排序规则存放相应节点 int in[1005];//入度 int dis[1005];//到达每个节点的最大距离 int map[1005][1005];//储存节点信息 int cnt[1005][1005];//储存输入顺序，方便输出 int n,m;//n为节点数，m为边数 void front_handle()// 处理队列的前端节点 { while(!q.empty())//遍历队列 { int top=q.front(); q.pop(); for(int i=vec[top].size()-1;i>=0;i--) { int node=vec[top][i].node; int time=vec[top][i].time; in[node]--; if(!in[node]) q.push(node);//node的所有前序节点都遍历完，将node压入队列 if(dis[top]+time>dis[node]) { dis[node]=dis[top]+time; } } }}void dfs(int x)//深度遍历寻找关键活动 { if(!dis[x]) return; for(int i=1;i<=n;i++) { if(map[i][x]&&dis[i]+map[i][x]==dis[x])//关键活动的判断条件 { sets.insert(S(i,x,cnt[i][x])); dfs(i); } }}int main(){ cin>>n>>m; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; map[x][y]=z; cnt[x][y]=i; in[y]++; vec[x].push_back(Node(y,z)); } for(int i=1;i<=n;i++) { if(!in[i]) q.push(i); } front_handle(); bool flag=true; int max=0; for(int i=1;i<=n;i++) { if(in[i])//如果还有节点未处理，那么该方案不可行 { flag=false; break; } if(dis[i]>max) max=dis[i]; } if(!flag) { cout<<0<
           
            ::iterator it=sets.begin();it!=sets.end();it++) { cout<
            
             x<<"->"<
             
              y<
             
            
           
          
        
       
      
     
    
   

总结

本文章参考了这篇文章——

需要说明的是，我认为原文章的变量以及函数命名比较随意，对于读者的理解没有什么帮助。所有我对其进行了优化并加上了注释，方便大家理解