A26402. 工作规划
填空题
困难
知识点
题目描述
工作规划
题目描述
n 台机器人正在完成任务。其中，第 i 台机器人需要工作 ti 分钟才能完成任务。这些机器人之间有一些前后约束，其中约束关系共有m条，每一条约束表示机器人 b 要在机器人 a 完成任务后才能开始工作。
请问，所有机器人任务完成最少需要花多少时间。保证所有约束之间均是合理的，所有机器人一定在有限时间内完成工作。
输入格式
第一行：两个整数 n 和 m
第二行到第 n+1 行：每个机器人需要的时间 ti
接下来 m 行：每行有两个整数 a 和 b，表示第 b 台机器人必须要等第 a 台机器人任务完成之后才能开始工作。
输出格式
单个整数，表示所有机器人任务完成最少需要花多少时间。
输入样例
10 9
3
29
1
35
18
22
8
29
4
12
3 2
4 8
1 7
6 5
7 10
8 1
10 9
2 4
5 3输出样例
161说明提示
1≤n≤104，1≤m≤50,000，1≤ti≤105，1≤ai,bi≤n
参考答案
#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;
}
上一题
下一题