A3597 | $作业调度方案$

来源NOIP提高组 / 2006

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

我们现在要利用m台机器加工n个工件，每个工件都有m道工序，每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。 每个工件的每个工序称为一个操作，我们用记号j-k表示一个操作，其中j为1到n中的某个数字，为工件号；k为1到m中的某个数字，为工序号，例如2-4表示第2个工件第4道工序的这个操作。在本题中，我们还给定对于各操作的一个安排顺序。 例如，当n=3，m=2时，“1-1，1-2，2-1，3-1，3-2，2-2”就是一个给定的安排顺序，即先安排第1个工件的第1个工序，再安

每组输入数据的第1行为两个正整数，用一个空格隔开： m n （其中m（ <20）表示机器数，n（ <20）表示工件数） 第2行：m*n个用空格隔开的数，为给定的安排顺序。 接下来的2n行，每行都是用空格隔开的m个正整数，每个数不超过20。其中前n行依次表示每个工件的每个工序所使用的机器号，第1个数为第1个工序的机器号，第2个数为第2个工序机器号，等等。后n行依次表示每个工件的每个工序的加工时间。 可以保证，以上各数据都是正确的，不必检验。

每组输出只有一个正整数，为最少的加工时间。

输入 #1

2 3
1 1 2 3 3 2
1 2
1 2
2 1
3 2
2 5
2 4

输出 #1

C++ 编辑器

输入

输出