Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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 C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D DART ELIXIR FANTOM FORTH GRV KTLN LUA NODEJS OBJC OCAML OCT PAS-FPC PIKE PROLOG R RACKET CHICKEN ST SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.