Đăng ký
cpp-101Đọc toàn bộ đề miễn phí

Thuật toán Hungary: Cặp ghép hoàn hảo trọng số cực tiểu O(N^3)

Có N công việc và N công nhân. Chi phí để công nhân i thực hiện công việc j là Ci, j. Mỗi công nhân chỉ làm đúng 1 việc và mỗi việc chỉ được giao cho đúng 1 công nhân. Hãy tìm c…

C++Nâng cao55 phút

Tiến độ của tôi ở bài này

Điểm được lưu vào tài khoản sau khi chấm bài.

Đang tải điểm của bạn…

Kiến thức và chủ đề

graphsbipartite matchinghungarian algorithmmin cost

Kiến thức tiên quyết: bipartite matching, graphs.

Nội dung đề bài

Mục tiêu kiến thức

  • Hiểu bài toán Gán việc tối ưu (Assignment Problem) trên đồ thị hai phía đầy đủ KN, N với trọng số cạnh.
  • Nắm vững thuật toán Hungary (Kuhn-Munkres) tìm cặp ghép hoàn hảo có tổng trọng số cực tiểu trong thời gian O(N3) sử dụng thế vị (potentials).

Mô tả bài toán

Có N công việc và N công nhân. Chi phí để công nhân i thực hiện công việc j là Ci, j. Mỗi công nhân chỉ làm đúng 1 việc và mỗi việc chỉ được giao cho đúng 1 công nhân. Hãy tìm cách phân công sao cho tổng chi phí là nhỏ nhất.

Quy ước nộp bài

  • Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
  • Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
  • Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
  • Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Input

  • Dòng 1: Một số nguyên N (1 ≤ N ≤ 300).
  • N dòng tiếp theo: Mỗi dòng gồm N số nguyên mô tả ma trận chi phí Ci, j (0 ≤ Ci, j ≤ 106).

Output

  • In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Ràng buộc

  • 1 ≤ N ≤ 300.
  • Thời gian: 1000ms. Bộ nhớ: 256MB.

Ví dụ 1

Input

3
1 4 5
5 7 6
5 8 8

Output

15
*Giải thích: Phân công công nhân 1 làm việc 1 (chi phí 1), công nhân 2 làm việc 3 (chi phí 6), công nhân 3 làm việc 2 (chi phí 8) $\implies 1 + 6 + 8 = 15$.*
3 cấp độ gợi ýMở dần khi bạn thật sự cần hỗ trợ.
Phân tích lời giảiGiải thích hướng tư duy và thuật toán.
Code tham khảoDùng để đối chiếu sau khi tự làm.

Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.

Bài tập liên quan cùng chuyên đề

Cặp ghép cực đại trên đồ thị hai phía bằng thuật toán Kuhn
Nâng cao40p
Lát cắt hẹp nhất toàn cục: Thuật toán Stoer-Wagner O(V^3)
Nâng cao50p
Cây Gomory-Hu: Biểu diễn lát cắt hẹp nhất giữa mọi cặp đỉnh
Nâng cao60p
Luồng cực đại trên mạng bằng thuật toán Edmonds-Karp
Nâng cao45p

Góp ý & báo lỗi bài tập

Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.