|
|
Từ tập các bài có trên SPOJ (acm)
684. Another Assignment Problem
Mã bài: ASSIGN4
|
Assume that you are a manager and there are m types of worker (numbered from 1 to m) and n types of task (numbered from 1 to n). There are a(i) workers of type #i and b(j) postitions for task #j. C(i, j) is the cost of hiring a worker of type #i to do the task of type #j. Your job is to minimize the cost of hiring workers to fill all the positions given that the total number of workers is equal to the total number of positions.
Input
The first line of input contains the number of test cases nTest (1<= nTest <= 10).
Each test case contains:
- The first line contains the number of worker types - m and number of task types - n.
- The second line contains m positive integers: a(1), a(2), ..., a(m).
- The third line contains n positive integers: b(1), b(2), ..., b(n).
- Each of the next m lines contains n integers describing matrix C(i, j).
Notes:
1 <= m, n <= 200;
1 <= a(i), b(i) <= 30000;
1 <= C(i, j) <= 10000.
Sum of a(i) equals to sum of b(j).
Output
For each test case write the minimum cost in a separate line (it will fit in a signed 32-bit integer).
Example
Input:
2
3 4
3 6 7
2 5 1 8
1 2 3 4
8 7 6 5
9 12 10 11
4 4
1 3 5 7
2 4 2 8
1 4 7 3
4 7 5 3
5 7 8 3
5 3 6 8
Output:
110
54
| Được gửi lên bởi: | Nguyen Dinh Tu |
| Ngày: | 2006-01-02 |
| Thời gian chạy: | 5s
|
| Giới hạn mã nguồn: | 50000B |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: AWK CLOJ ERL F# GO PERL 6 PYTH 3.1.2 SCALA SED TCL |
| Nguồn bài: | Tran Quang Khai |
|
|
|
|
