中国大学MOOC-数据结构基础习题集、06-4、How Long Does It Take

题目链接：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 <iostream>
 2 #include <algorithm>
 3 #include <vector>
 4 #include <queue>
 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<n; i++)
29     {
30         Indegree[i] = 0;
31         earlist[i] = 0;
32     }
33 
34     vector<node> vec;
35 
36     for(int i=0; i<m; i++)
37     {
38         int a, b, c;
39         cin >> 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<int> Q;
47 
48     for(int V=0; V<n; V++)
49         if ( Indegree[V] == 0)
50             Q.push(V);
51 
52     int cnt = 0;
53 
54     while( Q.size() != 0)
55     {
56         int V = Q.front();
57         Q.pop();
58         cnt++;
59         for ( int i=0; i<m; i++ )
60         {
61             if ( vec[i].s == V)
62             {
63                 int W = vec[i].e;
64                 earlist[W] = max(earlist[W], earlist[V] + vec[i].l);
65                 if ( --Indegree[W] == 0)
66                     Q.push(W);
67             }
68         }
69 
70     }
71 
72     if ( cnt != n )
73     {
74         cout << "Impossible" << endl;
75     }
76     else
77     {
78         cout << *max_element(earlist, earlist+n) << endl;
79     }
80     return 0;
81 }

AC成果：