题目链接：http://www.patest.cn/contests/mooc-ds/06-4

题目分析：这是一道考察图的拓扑排序问题，输入是图的相关信息，输出最早结束时间或者Impossible。题目还是比较简单的。

特别说明：

　　1. 输出最大值，可以用标准库的函数：max_element，返回值是地址，所以需要*把内容取出来。如数组a[n]，最大值为：*max_element(earlist, earlist+n)。当然不是求数组的最大值，而是求vector的最大值，只需要传相应的迭代器就可以。

　　2. 同理，两者之中想求得最大值，可以直接max(a, b)返回的就是最大值了，当然注意不同类型的不能比较哦（除非重载过<）。

　　3. 如果case2错误的话，注意earlist最大的，不一定是最后一个，要输出max_element(earlist, earlist+n)，而不是earlist[n-1]。

　　4. 如果case4错误的话，关注一下本代码64行，看看是不是忘记用max函数了（或者其他等价的函数）。

64 　　earlist[W] = max(earlist[W], earlist[V] + vec[i].l);　

代码分析：

　　头文件及结构体声明：1~15

　　cmp函数（用于sort排序函数的子函数）：16~20

　　最早完成时间、入度数组的动态申请及初始化：21~33

　　每个活动的s，e，l的输入处理：34~43

　　sort函数用于排序，把终点相同的活动集中在一起：44

　　拓扑排序：45~71

　　判断是否存在回路并输出结果：72~81

　　

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5  6 using namespace std; 7  8 struct node 9 {10     int s;11     int e;12     int l;13     node(int a, int b, int c):s(a), e(b), l(c) {}14 };15 16 int cmp(const node &a, const node &b)17 {18     return a.e < b.e;19 }20 21 int main()22 {23     int n, m;24     cin >> n >> m;25     int *earlist = new int[n];26     int *Indegree = new int[n];27 28     for(int i=0; i
         
           vec;35 36     for(int i=0; i
          
           > a >> b >> c;40 Indegree[b] ++;41 vec.push_back(node(a, b, c));42 }43 44 sort(vec.begin(), vec.end(), cmp);45 46 queue
           
             Q;47 48 for(int V=0; V
           
          
         
        
       
      
     

 

AC成果：