← 返回题目

题库练习牛奶调度

← 上一题下一题 →

A2781 | $牛奶调度$

来源USACO / 2013

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

农民约翰有N头奶牛(1<=N<=10,000)，编号为1...N。每一头奶牛需要T(i)单位的时间来挤奶。不幸的是，由于FJ的仓库布局，一些奶牛要在别的牛之前挤奶。比如说，如果奶牛A必须在奶牛B前挤奶，FJ就需要在给奶牛B挤奶前结束给奶牛A的挤奶。 为了尽量完成挤奶任务，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。这些约束永远不会形成一个循环，因此解决方案总是可能的。

输出格式

* 第 1 行：为所有奶牛挤奶所需的最短时间。

输入输出样例

输入 #1

输出 #1

C++ 编辑器

输入

输出