首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#13162

工作规划 题目描述 n 台机器人正在完成任务。其中,第 i 台机器人需要工作 t i 分钟才能完成任务。这些机器人之间有一些前后约束,其中约束关系共有m条,每一…

工作规划

题目描述

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

限制

时间限制:1000ms

内存限制:512MiB

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; #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-&gt;to = v;    new_node-&gt;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 &lt;= n; i++) {        if (in_degree[i] == 0) {            queue[rear++] = i;            earliest_start[i] = 0;  // 入度为0的节点最早开始时间为0        }    }    // 处理队列中的节点    while (front &lt; rear) {        int u = queue[front++];        // 遍历所有后继节点        Node* current = adj[u];        while (current != NULL) {            int v = current-&gt;to;            // 更新后继节点的最早开始时间            if (earliest_start[v] &lt; 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-&gt;next;        }    }    // 计算最大最早完成时间    int max_time = 0;    for (int i = 1; i &lt;= n; i++) {        int finish_time = earliest_start[i] + t[i];        if (finish_time &gt; 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", &amp;n, &amp;m);    for (int i = 1; i &lt;= n; i++) {        scanf("%d", &amp;t[i]);    }    for (int i = 0; i &lt; m; i++) {        int a, b;        scanf("%d %d", &amp;a, &amp;b);        add_edge(a, b);    }    // 计算并输出结果    int result = topological_sort();    printf("%d\n", result);    // 释放内存    for (int i = 1; i &lt;= n; i++) {        Node* current = adj[i];        while (current != NULL) {            Node* temp = current;            current = current-&gt;next;            free(temp);        }    }    return 0; }</pre>
这道题暂未补解析。