[Tin học] Xây dựng trường Chuyên Bến Tre

2. Đề bài về cặp ghép cực đại có trọng số nhỏ nhất

Trường THPT Chuyên Bến Tre ra quyết định xây dựng trường chuyên mới. Ban giám hiệu quyết định trả tiền ngay trong ngày cho các nhà thầu.  Có n công trình và n nhà thầu tham gia đấu thầu công trình. Biết thời gian xây dựng công trình của các nhà thầu là khác nhau. Vì số ngày làm ảnh hưởng đến chi phí nên nhà trường quyết định chọn các nhà thầu thích hợp để tổng chi phí phải trả cho mỗi nhà thầu là thấp nhất.

Yêu cầu: Hãy cho biết tổng thời gian nhỏ nhất và lịch phân công.

Dữ liệu vào

CHUYENBT.INP

  • Dòng 1: chứa số n (1<=n<=200)
  • Các dòng tiếp theo, mỗi dòng chứa 3 số nguyên u,v,c cho biết nhà thầu u ra giá cho công trình v là c (0<=c<=200, 1<=u,v<=200)

Dữ liệu ra

CHUYENBT.OUT

  • Dòng đầu chứa số S là tổng thời gian nhỏ nhất tìm được.
  • N dòng tiếp theo, mỗi dòng gồm 2 số u, v cho biết nhà thầu u sẽ đảm nhận công trình v (lịch phân công tối ưu nhất theo S).

Example

Input

4

1 1 0

1 2 0

2 1 0

2 4 2

3 2 1

3 3 0

4 3 0

4 4 9

Output

3

1 1

2 4

3 2

4 3

2. Hướng dẫn Hungari

  • Đây là dạng bài toán phân công tối ưu.
  • Áp dụng thuật toán Hungari tìm cặp ghép cực đại có trọng số nhỏ nhất

3. Code tham khảo Hungari

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *