7-11 关键活动 (30 分)
假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。
比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和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
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
| #include<stdio.h>
#include<stdlib.h>
#define MAXVER 105
#define INFINITY 65535
int G[MAXVER][MAXVER];
int early[MAXVER];
int late[MAXVER];
int in[MAXVER];
int out[MAXVER];
int nv,ne;
void CreatGraph();
int EarlyTime();
void LateTime(int Scost);
int FindMax( int a,int b);
int FindMin( int a,int b);
int main()
{
int flag;
int i,j;
scanf("%d %d",&nv,&ne);
CreatGraph();
flag = EarlyTime();
if( flag==-1)
{
printf("0\n");
}
else
{
printf("%d\n",flag);
LateTime( flag );
for( i=1; i<=nv; i++)
{
if(early[i] != late[i])
continue;
for( j=nv; j>=1 ; j--)
{
if( G[i][j]>=0 && early[j]==late[j] &&late[j]-G[i][j]==early[i])
{
printf("%d->%d\n",i,j);
}
}
}
}
return 0;
}
void CreatGraph()
{
int i,j;
int s,d,cost;
for( i=1; i<=nv; i++)
{
for( j=1; j<=nv; j++)
{
G[i][j] = -1;
}
early[i] = 0;
late[i] = INFINITY;
in[i] = 0;
out[i] = 0;
}
for( i=0; i<ne; i++)
{
scanf("%d %d %d",&s,&d,&cost);
G[s][d] = cost;
in[d] ++;
out[s]++;
}
}
int EarlyTime()
{
int queue[nv];
int first =-1,rear = -1;
int count=0;
int i;
int temp,ret=0;
for( i=1; i<=nv; i++)
{
if( in[i]==0)
{
queue[++rear] = i;
}
}
while( first<rear)
{
temp = queue[++first];
count++;
for( i=1; i<=nv; i++)
{
if( G[temp][i]>=0 )
{
in[i]--;
early[i] = FindMax( early[i],early[temp]+G[temp][i]);
if( in[i]==0)
{
queue[++rear] = i;
}
}
}
}
if( count!=nv)
{
ret = -1;
}
else
{
ret = early[1];
for( i=2; i<=nv; i++)
{
if(early[i] > ret)
{
ret = early[i];
}
}
}
return ret;
}
void LateTime(int Scost)
{
int i;
int queue[MAXVER];
int first=-1,rear=-1;
int temp;
for( i=1; i<=nv; i++)
{
if( out[i]==0)
{
queue[++rear] = i;
late[i] = Scost;
}
}
while( first<rear )
{
temp = queue[++first];
for( i=nv; i>=1; i--)
{
if( G[i][temp]>=0)
{
late[i] = FindMin( late[i],late[temp]-G[i][temp]);
out[i]--;
if(out[i]==0)
{
queue[++rear] = i;
}
}
}
}
}
int FindMax( int a,int b)
{
if( a>b )
{
return a;
}
else
{
return b;
}
}
int FindMin( int a,int b)
{
if( a>b )
{
return b;
}
else
{
return a;
}
}
|
