A2781. 牛奶调度
编程题
普及/提高-
知识点
题目描述
农民约翰有N头奶牛(1<=N<=10,000)，编号为1...N。每一头奶牛需要T(i)单位的时间来挤奶。不幸的是，由于FJ的仓库布局，一些奶牛要在别的牛之前挤奶。比如说，如果奶牛A必须在奶牛B前挤奶，FJ就需要在给奶牛B挤奶前结束给奶牛A的挤奶。
为了尽量完成挤奶任务，FJ聘请了一大批雇工协助任务——同一时刻足够去给任意数量的奶牛挤奶。然而，尽管奶牛可以同时挤奶，但仍需要满足以上的挤奶先后顺序。请帮助FJ计算挤奶过程中的最小总时间。
为了尽量完成挤奶任务，FJ聘请了一大批雇工协助任务——同一时刻足够去给任意数量的奶牛挤奶。然而，尽管奶牛可以同时挤奶，但仍需要满足以上的挤奶先后顺序。请帮助FJ计算挤奶过程中的最小总时间。
输入格式
* 第 1 行：两个空格分隔的整数：N（奶牛数量）和 M（挤奶约束数量;1 <= M <= 50,000）。
* 第 2..1+N 行：第 i+1 行包含 T（i） 的值 （1 <= T（i） <= 100,000）。
* 第 2+N 行。1+N+M：每行包含两个空格分隔的整数 A 和 B，表示奶牛 A 必须完全挤奶，然后才能开始挤奶奶牛 B。这些约束永远不会形成一个循环，因此解决方案总是可能的。
* 第 2..1+N 行：第 i+1 行包含 T（i） 的值 （1 <= T（i） <= 100,000）。
* 第 2+N 行。1+N+M：每行包含两个空格分隔的整数 A 和 B，表示奶牛 A 必须完全挤奶，然后才能开始挤奶奶牛 B。这些约束永远不会形成一个循环，因此解决方案总是可能的。
输出格式
* 第 1 行：为所有奶牛挤奶所需的最短时间。
输入输出样例
输入 #1
3 1 10 5 6 3 2
输出 #1
11
说明/提示
有3头奶牛。每头奶牛挤奶所需的时间分别为 10、5 和 6。奶牛 3 必须完全挤奶，然后才能开始挤奶 2。
奶牛 1 和 3 最初可以同时挤奶。当奶牛 3 完成挤奶后，奶牛 2 就可以开始挤奶了。所有奶牛在经过 11 个单位的时间后完成挤奶。
奶牛 1 和 3 最初可以同时挤奶。当奶牛 3 完成挤奶后，奶牛 2 就可以开始挤奶了。所有奶牛在经过 11 个单位的时间后完成挤奶。