答案:<pre class="brush:cpp;toolbar:false">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 10005
#define MAX_M 50005
#define INF 0x3f3f3f3f
typedef struct Node {
int to;
struct Node* next;
} Node;
Node* adj[MAX_N]; // 邻接表
int in_degree[MAX_N]; // 入度数组
int t[MAX_N]; // 每个机器人的工作时间
int earliest_start[MAX_N]; // 每个机器人的最早开始时间
int n, m;
// 添加边
void add_edge(int u, int v) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->to = v;
new_node->next = adj[u];
adj[u] = new_node;
in_degree[v]++;
}
// 拓扑排序计算最早完成时间
int topological_sort() {
int queue[MAX_N];
int front = 0, rear = 0;
// 初始化队列,将入度为0的节点加入队列
for (int i = 1; i <= n; i++) {
if (in_degree[i] == 0) {
queue[rear++] = i;
earliest_start[i] = 0; // 入度为0的节点最早开始时间为0
}
}
// 处理队列中的节点
while (front < rear) {
int u = queue[front++];
// 遍历所有后继节点
Node* current = adj[u];
while (current != NULL) {
int v = current->to;
// 更新后继节点的最早开始时间
if (earliest_start[v] < earliest_start[u] + t[u]) {
earliest_start[v] = earliest_start[u] + t[u];
}
// 减少后继节点的入度
in_degree[v]--;
if (in_degree[v] == 0) {
queue[rear++] = v;
}
current = current->next;
}
}
// 计算最大最早完成时间
int max_time = 0;
for (int i = 1; i <= n; i++) {
int finish_time = earliest_start[i] + t[i];
if (finish_time > max_time) {
max_time = finish_time;
}
}
return max_time;
}
int main() {
// 初始化
memset(adj, 0, sizeof(adj));
memset(in_degree, 0, sizeof(in_degree));
memset(earliest_start, 0, sizeof(earliest_start));
// 读取输入
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &t[i]);
}
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d %d", &a, &b);
add_edge(a, b);
}
// 计算并输出结果
int result = topological_sort();
printf("%d\n", result);
// 释放内存
for (int i = 1; i <= n; i++) {
Node* current = adj[i];
while (current != NULL) {
Node* temp = current;
current = current->next;
free(temp);
}
}
return 0;
}</pre>
这道题暂未补解析。