| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
MTTTHO - Tuyển công nhân |
Có n công việc cần thực hiện và r loại thợ. Thợ loại i có thể không làm được việc j hoặc làm được với chi phí là c[i,j]. Một phép phân công là một cách chọn ra n thợ và giao cho mỗi thợ làm đúng một việc sao cho có thể thực hiện tất cả n công việc.
Giả sử đã có sẵn m thợ hãy tìm cách tuyển thêm một số ít nhất thợ để có thể thực hiện phép phân công. Nếu có nhiều cách tuyển thoả mãn yêu cầu trên thì chỉ ra cách tuyển có tổng chi phí thực hiện các công việc (trên phép phân công tối ưu) là cực tiểu.
Dữ liệu: Vào từ file văn bản ASSIGN.INP
- Dòng 1: Chứa ba số m, n, r (1 <= m, n, r <= 300)
- Dòng 2: Chứa m số, số thứ k là loại của thợ thứ k trong m thợ đã có
- Các dòng tiếp theo, mỗi dòng ghi ba số i, j, c[i,j] cho biết loại thợ i có thể làm được việc j với chi phí c[i,j] (0 <= c[i,j] <= 10000)
Các số trên một dòng của Input file cách nhau ít nhất một dấu cách
Kết quả: Ghi ra file văn bản ASSIGN.OUT
- Dòng 1: Ghi số thợ cần thêm và chi phí phép phân công tối ưu
- n dòng tiếp theo, dòng thứ i ghi loại thợ được giao thực hiện việc i
Ràng buộc: Mỗi việc có ít nhất một loại thợ có thể thực hiện
Ví dụ:
|
ASSIGN.INP |
ASSIGN.OUT |
|
ASSIGN.INP |
ASSIGN.OUT |
|
10 4 6 1 3 5 5 5 5 5 5 5 5 1 1 10 1 2 10 1 3 10 3 1 10 3 2 10 3 3 10 2 2 9 2 1 8 4 2 6 4 3 5 6 4 0 |
2 25 1 3 4 6
|
|
1 2 3 1 1 1 10 1 2 30 3 1 1 3 2 25 2 2 40
|
1 31 3 1
|
| Được gửi lên bởi: | Đặng Minh Tiến |
| Ngày: | 2014-12-21 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC MAWK BC C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D DART ELIXIR FANTOM FORTH GRV JULIA KTLN LUA NODEJS OBJC OCAML OCT PAS-FPC PIKE PROLOG PYPY3 R RACKET CHICKEN ST SQLITE SWIFT UNLAMBDA |
