中国大学MOOC-数据结构基础习题集、06-5、关键活动

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

题目分析：这是一道考察图的拓扑排序——关键路径问题。在作业06-4的基础上不仅要求每个点的最早开始时间，还要求每个点的最晚结束时间，除此之外，还要知道每个活动的最早开始、最晚结束时间。活动的最早和最晚时间相等的活动，才是关键活动。

特别说明：

　　1. 这道题最关键的地方，就是在于整个活动的结束结点，并不一定是最后一个结点，而是earlist的中最大的那一个。所以如果你还想博主，latest[n-1]=earlist[n-1]，那就大错特错了，最起码最后一个case通不过去。求earlist最大值的代码如下：

1 　　int maxNumber = *max_element(earlist+1,earlist+n);

　　1.1 其实不一定要知道earlist数组中最大值的下标，只需要把这个最大值赋给latest数组的每一个元素就可以了，快捷方式如下：

1     fill(latest+1, latest+n, maxNumber);

　　接下来我们就可以对出度为0的结点进行“拓扑排序”了。

　　2. 这道题最最关键的地方，就是case1（也就是测试用例2）的那个奇怪的输出。我们要做的第一步，就是在输入的时候，把输入次序也存起来。在输入的时候，我们不妨将入度、出度都计算好。

1     for(int i=0; i<m; i++)
2     {
3         int a, b, c;
4         cin >> a >> b >> c;
5         Outdegree[a] ++;
6         Indegree[b] ++;
7         vec.push_back(node(i, a, b, c));
8     }

　　2.1 我们首先不管那个“反序”，先将“正序”路径放在vector中。

 1     typedef pair<int, int> PAIR;
 2     vector<PAIR> route;
 3     for(int i=0; i<m; i++)
 4     {
 5         int j = vec[i].s;
 6         int k = vec[i].e;
 7         e[i] = earlist[j];
 8         l[i] = latest[k] - vec[i].l;
 9         if(e[i] == l[i])
10         {
11             route.push_back(PAIR(j, k));
12         }
13     }

　　2.2 接着，对route排序，按照起点升序排序：

14     sort(route.begin(), route.end());

　　2.3 接着，利用一个临时的容器routeTemp，将起点相同的按照输入反序输出。flag标记是否是第一次，lastNum记录上次的起点，分为以下三种情况：

　　2.3.1 如果flag=true，证明是第一次，lastNum=j，并且把这条的路径压入routeTemp中。

　　2.3.2 如果flag=false并且j与lastNum不等，将routeTemp中按照输入次序从大到小排序（这个顺序我们在输入的时候就已经指定好了，可以使用sort和cmp函数很方便的排序），并且输出routeTemp中所有路径，清空routeTemp，且将当前路径压入routeTemp中。

　　2.3.2 如果flag=false并且j与lastNum相同，将当前路径压入routeTemp中。

 1     vector<node> routeTemp;
 2     int lastNum;
 3     int flag = true;
 4     for(int i=0; i<route.size(); i++)
 5     {
 6         int j = route[i].first;
 7         int k = route[i].second;
 8         if(flag == true)
 9         {
10             flag = false;
11             lastNum = j;
12 
13             for(int icount=0; icount<m; icount++)
14             {
15                 if(vec[icount].s == j && vec[icount].e == k)
16                 {
17                     routeTemp.push_back(vec[icount]);
18                     break;
19                 }
20             }
21         }
22         else if(flag == false && j != lastNum)
23         {
24             sort(routeTemp.begin(), routeTemp.end(), cmpForRoute);
25             for(int i=0; i<routeTemp.size(); i++)
26             {
27                 cout << routeTemp[i].s << "->" << routeTemp[i].e << endl;
28             }
29             routeTemp.clear();
30             for(int icount=0; icount<m; icount++)
31             {
32                 if(vec[icount].s == j && vec[icount].e == k)
33                 {
34                     routeTemp.push_back(vec[icount]);
35                     break;
36                 }
37             }
38             lastNum = j;
39         }
40         else if(flag == false && j == lastNum)
41         {
42             for(int icount=0; icount<m; icount++)
43             {
44                 if(vec[icount].s == j && vec[icount].e == k)
45                 {
46                     routeTemp.push_back(vec[icount]);
47                     break;
48                 }
49             }
50         }
51     }

代码分析：

　　前面的特别说明已经很详细的解释了本题的重点，相信看过的童鞋对此题已经有了想法。如果你的思路已经明确的话，就不要继续看了，赶紧做题去。如果对整体把握不是那么好的话，不妨阅读一下整体的代码。相关注释已经打好，就不再赘述了。

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <vector>
  4 #include <queue>
  5 
  6 #define MAXNUM 100000000
  7 using namespace std;
  8 
  9 struct node
 10 {
 11     int i;  //用来标记次序
 12     int s;
 13     int e;
 14     int l;
 15     node(int ii, int a, int b, int c):i(ii), s(a), e(b), l(c) {}
 16 };
 17 
 18 int cmp(const node &a, const node &b)
 19 {
 20     return a.e < b.e;
 21 }
 22 
 23 int cmpForRoute(const node &a, const node &b)
 24 {
 25     if(a.s != b.s)
 26         return a.s < b.s;
 27     else
 28         return a.i > b.i;
 29 }
 30 
 31 int main()
 32 {
 33     int n, m;
 34     cin >> n >> m;
 35     n ++;
 36     // earlist 最早完成时间
 37     int *earlist = new int[n];
 38     // latest 最晚完成时间
 39     int *latest = new int[n];
 40     // Indegree 入度
 41     int *Indegree = new int[n];
 42     // Outdegree 出度
 43     int *Outdegree = new int[n];
 44     // 初始化
 45     for(int i=0; i<n; i++)
 46     {
 47         Indegree[i] = 0;
 48         Outdegree[i] = 0;
 49         earlist[i] = 0;
 50         latest[i] = MAXNUM;
 51     }
 52 
 53     vector<node> vec;
 54 
 55     for(int i=0; i<m; i++)
 56     {
 57         int a, b, c;
 58         cin >> a >> b >> c;
 59         Outdegree[a] ++;
 60         Indegree[b] ++;
 61         vec.push_back(node(i, a, b, c));
 62     }
 63 
 64     sort(vec.begin(), vec.end(), cmp);
 65 
 66     queue<int> Q;
 67     // 将所有入度为0的点放入队列中
 68     for(int V=1; V<n; V++)
 69         if(Indegree[V] == 0)
 70             Q.push(V);
 71     // 记录有多少个点，用来判断是否有回路
 72     int cnt = 0;
 73     // 正向求最早完成时间
 74     while( Q.size() != 0)
 75     {
 76         int V = Q.front();
 77         Q.pop();
 78         cnt++;
 79         for ( int i=0; i<m; i++ )
 80         {
 81             if ( vec[i].s == V)
 82             {
 83                 int W = vec[i].e;
 84                 earlist[W] = max(earlist[W], earlist[V] + vec[i].l);
 85                 if ( --Indegree[W] == 0)
 86                     Q.push(W);
 87             }
 88         }
 89     }
 90     // 判断是否有环
 91     if ( ++cnt != n  )
 92     {
 93         cout << "0" << endl;
 94         return 0;
 95     }
 96     // 反向求最晚完成时间，出度为0的结点就是终点了
 97     for(int V=1; V<n; V++)
 98         if(Outdegree[V] == 0)
 99             Q.push(V);
100     // 将最后一个结点的earlist赋值给latest
101     int maxNumber = *max_element(earlist+1,earlist+n);
102     cout << maxNumber << endl;
103     fill(latest+1, latest+n, maxNumber);
104     while( Q.size() != 0)
105     {
106         int W = Q.front();
107         Q.pop();
108         cnt++;
109         for ( int i=0; i<m; i++ )
110         {
111             if ( vec[i].e == W)
112             {
113                 int V = vec[i].s;
114                 latest[V] = min(latest[V], latest[W] - vec[i].l);
115                 if ( --Outdegree[V] == 0)
116                     Q.push(V);
117             }
118         }
119     }
120     // 求每个活动的e[i]和l[i]
121     int *e = new int [m];
122     int *l = new int [m];
123     fill(e, e+m, 0);
124     fill(l, l+m, 0);
125     // 将路径存储在vector容器里
126     typedef pair<int, int> PAIR;
127     vector<PAIR> route;
128     for(int i=0; i<m; i++)
129     {
130         int j = vec[i].s;
131         int k = vec[i].e;
132         e[i] = earlist[j];
133         l[i] = latest[k] - vec[i].l;
134         if(e[i] == l[i])
135         {
136             route.push_back(PAIR(j, k));
137         }
138     }
139     // 为了应付那个奇怪的输出，需要对容器排序
140     sort(route.begin(), route.end());
141     // 临时存储路径，用来反序输出
142     vector<node> routeTemp;
143     int lastNum;
144     int flag = true;
145     for(int i=0; i<route.size(); i++)
146     {
147         int j = route[i].first;
148         int k = route[i].second;
149         if(flag == true)
150         {
151             flag = false;
152             lastNum = j;
153 
154             for(int icount=0; icount<m; icount++)
155             {
156                 if(vec[icount].s == j && vec[icount].e == k)
157                 {
158                     routeTemp.push_back(vec[icount]);
159                     break;
160                 }
161             }
162         }
163         else if(flag == false && j != lastNum)
164         {
165             sort(routeTemp.begin(), routeTemp.end(), cmpForRoute);
166             for(int i=0; i<routeTemp.size(); i++)
167             {
168                 cout << routeTemp[i].s << "->" << routeTemp[i].e << endl;
169             }
170             routeTemp.clear();
171             for(int icount=0; icount<m; icount++)
172             {
173                 if(vec[icount].s == j && vec[icount].e == k)
174                 {
175                     routeTemp.push_back(vec[icount]);
176                     break;
177                 }
178             }
179             lastNum = j;
180         }
181         else if(flag == false && j == lastNum)
182         {
183             for(int icount=0; icount<m; icount++)
184             {
185                 if(vec[icount].s == j && vec[icount].e == k)
186                 {
187                     routeTemp.push_back(vec[icount]);
188                     break;
189                 }
190             }
191         }
192     }
193     // 将剩余元素依次输出
194     for(int i=0; i<routeTemp.size(); i++)
195     {
196         cout << routeTemp[i].s << "->" << routeTemp[i].e << endl;
197     }
198     return 0;
199 }

AC成果：