本实验项目是实验项目6-06的深化。任务调度问题中，如果还给出了完成每个子任务需要的时间，则我们可以算出完成整个工程需要的最短时间。在这些子任务中，有些任务即使推迟几天完成，也不会影响全局的工期；但是有些任务必须准时完成，否则整个项目的工期就要因此延误，这种任务就叫“关键活动”。
请编写程序判定一个给定的工程项目的任务调度是否可行；如果该调度方案可行，则计算完成整个工程项目需要的最短时间，并输出所有的关键活动。
输入格式说明：
输入第1行给出两个正整数N(<=100)和M，其中N是任务交接点（即衔接相互依赖的两个子任务的节点，例如：若任务2要在任务1完成后才开始，则两任务之间必有一个交接点）的数量，交接点按1~N编号，M是子任务的数量，依次编号为1~M。随后M行，每行给出了3个正整数，分别是该任务开始和完成涉及的交接点编号以及该任务所需的时间，整数间用空格分隔。
输出格式说明：
如果任务调度不可行，则输出0；否则第1行输出完成整个工程项目需要的时间，第2行开始输出所有关键活动，每个关键活动占一行，按格式“V->W”输出，其中V和W为该任务开始和完成涉及的交接点编号。关键活动输出的顺序规则是：任务开始的交接点编号小者优先，起点编号相同时，与输入时任务的顺序相反。如下面测试用例2中，任务<5,7>先于任务<5,8>输入，而作为关键活动输出时则次序相反。
样例输入与输出：
| 序号 | 输入 | 输出 |
| 1 | | |
| 2 | | |
| 3 | | |
| 4 | |
case3需要注意关键节点不一定是关键路径。
/*2015.7.17cyq*/
//关键路径
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
const int MAX=2147483647;
//ifstream fin("case3.txt");
//#define cin fin
struct node{
int early; //最早可以开始的时间
int late; //最晚必须开始的时间
int inDegree; //入度
int outDegree; //出度
vector<int> next;//后继结点
vector<int> pre; //前驱结点
node(int e,int l,int p,int n)://构造函数
early(e),late(l),inDegree(0),outDegree(0){}
};
int main(){
int N,M;
cin>>N>>M;
vector<vector<int> > edges(N+1,vector<int>(N+1,-1));
vector<node> G(N+1,node(0,MAX,0,0));//early=0,late=MAX
int a,b,c;
while(M--){
cin>>a>>b>>c;
edges[a][b]=c;
G[a].next.push_back(b);
G[b].pre.push_back(a);
G[b].inDegree++; //后继结点入度加1
G[a].outDegree++; //前驱结点出度加1
}
//从前往后计算每个结点最早可以开始的时间
queue<int> q;
int count=0; //记录入队的点的个数，若最后不是N个，说明无解
for(int i=1;i<=N;i++){
if(G[i].inDegree==0){
G[i].early=0;//开始时间为0
q.push(i); //入度为0的结点进入队列
count++;
}
}
while(!q.empty()){
int cur=q.front();//当前结点序号
q.pop();
//每个结点(*it)最早可以开始的时间受制于若干条前驱路径中
//花费时间最长的一条，就是等你等得最久啊啊啊
for(auto it=G[cur].next.begin();it!=G[cur].next.end();it++){
if(G[cur].early+edges[cur][*it] > G[*it].early)
G[*it].early=G[cur].early+edges[cur][*it];//更新
if(--G[*it].inDegree==0){
q.push(*it);
count++;
}
}
}
if(count!=N){
cout<<0<<endl;
return 0;
}
int completeTime=-1;//完成工程需要花费的总时间
for(int i=1;i<=N;i++){
if(G[i].early>completeTime)
completeTime=G[i].early;
}
cout<<completeTime<<endl;
//从后往前计算每个结点最晚必须开始的时间
for(int i=1;i<=N;i++){
if(G[i].outDegree==0){ //最后的结点，可能有多个
G[i].late=completeTime; //最晚必须开始的时间
q.push(i);
}
}
while(!q.empty()){
int cur=q.front();
q.pop();
//每个结点(*it)最晚必须开始的时间受制于若干条后继路径中
//花费时间最长的一条，因为该路径把deadline往前推得越多
for(auto it=G[cur].pre.begin();it!=G[cur].pre.end();it++){
if(G[*it].late > G[cur].late-edges[*it][cur])
G[*it].late = G[cur].late-edges[*it][cur];
if(--G[*it].outDegree==0)
q.push(*it);
}
}
vector<int> result;//关键节点
vector<bool> inResult(N+1,false);
for(int i=1;i<=N;i++){
if(G[i].early==G[i].late){
result.push_back(i);
inResult[i]=true;
}
}
for(auto it=result.begin();it!=result.end();++it){
for(auto itt=G[*it].next.rbegin();itt!=G[*it].next.rend();++itt){
if(inResult[*itt]&&(edges[*it][*itt]==G[*itt].early-G[*it].early))//关键路径，加上后半句才能过case3
cout<<*it<<"->"<<*itt<<endl;
}
}
return 0;
}
![树的基本概念(定义、基本术语、性质)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)