Scott's world.

关键活动

Word count: 1.5kReading time: 6 min
2019/09/09 Share

关键活动

假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。

比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程,各门课程可以看成是子任务。有些课程可以同时开设,比如英语和C程序设计,它们没有必须先修哪门的约束;有些课程则不可以同时开设,因为它们有先后的依赖关系,比如C程序设计和数据结构两门课,必须先学习前者。

但是需要注意的是,对一组子任务,并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B,子任务B依赖于子任务C,子任务C又依赖于子任务A”,那么这三个任务哪个都不能先执行,这就是一个不可行的方案。

任务调度问题中,如果还给出了完成每个子任务需要的时间,则我们可以算出完成整个工程需要的最短时间。在这些子任务中,有些任务即使推迟几天完成,也不会影响全局的工期;但是有些任务必须准时完成,否则整个项目的工期就要因此延误,这种任务就叫“关键活动”。

请编写程序判定一个给定的工程项目的任务调度是否可行;如果该调度方案可行,则计算完成整个工程项目需要的最短时间,并输出所有的关键活动。

输入格式:

输入第1行给出两个正整数N(≤100)和M,其中N是任务交接点(即衔接相互依赖的两个子任务的节点,例如:若任务2要在任务1完成后才开始,则两任务之间必有一个交接点)的数量。交接点按1~N编号,M是子任务的数量,依次编号为1~M。随后M行,每行给出了3个正整数,分别是该任务开始和完成涉及的交接点编号以及该任务所需的时间,整数间用空格分隔。

输出格式:

如果任务调度不可行,则输出0;否则第1行输出完成整个工程项目需要的时间,第2行开始输出所有关键活动,每个关键活动占一行,按格式“V->W”输出,其中V和W为该任务开始和完成涉及的交接点编号。关键活动输出的顺序规则是:任务开始的交接点编号小者优先,起点编号相同时,与输入时任务的顺序相反。

输入样例:

1
2
3
4
5
6
7
8
9
7 8
1 2 4
1 3 3
2 4 5
3 4 3
4 5 1
4 6 6
5 7 5
6 7 2

输出样例:

1
2
3
4
5
17
1->2
2->4
4->6
6->7

题目分析

这道题延续上一道题可以解出活动最早完成时间,但是这道题需要求出活动进行的顺序,我们当然可以在拓扑排序出记录活动的顺序,但是这只能解决一点关键路径的问题

这道题我们可以先做一次拓扑排序计算出各个入度且计算出每个活动的最早完成时间,然后我们可以再反过来做一次拓扑排序来计算出各个出度且算出每个活动的最晚时间,其实在这过程中也就计算出了所有活动的机动时间,当最后需要输出活动顺序时即输出关键路径时,机动时间为0的就是关键路径

题目代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
using namespace std;
#define MAX 100
#define INFINITY 65535
int N,M,A[MAX][MAX],ECT;
int index;
int EarlyTimes[MAX]= {0};
int D[MAX][MAX];

int getMax(int a[])
{
int value=a[0];
for(int i=1; i<N; i++)
{
if(value < a[i])
{
value=a[i];
index=i;
}
}
return value;
}

int TopSort()
{
int Indegree[MAX]= {0};
int cnt=0;
queue<int> q;
int V;

for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
{
if(A[i][j]!=INFINITY)
Indegree[j]++;
}

for(int i=0; i<N; i++)
{
if(Indegree[i]==0)
q.push(i);
}

while(!q.empty())
{
V=q.front();
q.pop();
cnt++;
for(int i=0; i<N; i++)
{
if(A[V][i]!=INFINITY)
{
if(EarlyTimes[V]+A[V][i]>EarlyTimes[i])
{
EarlyTimes[i]=EarlyTimes[V]+A[V][i];

}
if(--Indegree[i]==0)
{
q.push(i);
}
}
}
}
ECT=getMax(EarlyTimes);
if(cnt!=N)
return 0;
return 1;
}

void TopSort_reverse()
{
int V,Outdegree[MAX]= {0},LatestTimes[MAX];
queue<int>q;
//计算各结点的出度
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
if(A[i][j]!=INFINITY)
Outdegree[i]++;//累积起点i的入度
//处度为0的入队
for(int i=0; i<N; i++)
if(Outdegree[i]==0)
q.push(i);
//初始化LatestTimes
for(int i=0; i<N; i++)
LatestTimes[i]=INFINITY;
LatestTimes[index]=ECT; //将最后一个活动的最晚完成时间设置为它最早的完成时间
while(!q.empty())
{
V=q.front();
q.pop();
for(int j=0; j<N; j++)
{
if(A[j][V]!=INFINITY)
{
//必须用<=,只<的话只能算一条关键路径,<=才能算出所有的关键路径(错误原因)
if(LatestTimes[V]-A[j][V]<=LatestTimes[j])
{
LatestTimes[j]=LatestTimes[V]-A[j][V];
D[j][V]=LatestTimes[V]-EarlyTimes[j]-A[j][V];
}
if(--Outdegree[j]==0)
q.push(j);
}
}
}
for(int i=0; i<N; i++)
for(int j=N-1; j>=0; j--)
if(D[i][j]==0)
printf("%d->%d\n",i+1,j+1);
}

int main()
{
int Hash[MAX]= {0};
scanf("%d %d",&N,&M);

for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
A[i][j]= D[i][j] =INFINITY;

for(int i=0; i<M; i++)
{
int a,b;
scanf("%d %d",&a,&b);
scanf("%d",&A[a-1][b-1]);
}

if(!TopSort())
{
printf("0\n");
}
else
{
printf("%d\n",ECT);
TopSort_reverse();
}



return 0;
}
CATALOG
  1. 1. 关键活动
    1. 1.0.1. 输入格式:
    2. 1.0.2. 输出格式:
    3. 1.0.3. 输入样例:
    4. 1.0.4. 输出样例:
  2. 1.1. 题目分析
  3. 1.2. 题目代码