Nhờ chỉ cách làm tối ưu của bài Xếp Đôi

[linhmoi (lính mới)]

Đề bài:

Một chi đoàn nọ có M bạn nam và M bạn nữ, trong buổi giao lưu bí thư chi đoàn muốn xếp M cặp nam nữ để chơi trò chơi chung sức. M bạn trai, mỗi bạn sẽ cho bí thư biết mức độ tình cảm của họ với M bạn gái. Hãy giúp bí thư ghép cặp cho các bạn trai và các bạn gái sao cho tổng số mức độ tình cảm là lớn nhất

• Dữ liệu vào từ file XEPDOI.INP

  Dòng đầu tiên là số M (0<M<100). M dòng tiếp theo dòng i có M số theo thứ tự là mức độ tình cảm của bạn trai i-1 với các bạn gái 1…M.

• Dữ liệu ghi ra file XEPDOI.OUT

  Dòng đầu tiên là tổng mức độ tình cảm. Các dòng tiếp theo, mỗi dòng 3 số là chỉ số của bạn trai, bạn gái và mức độ tình cảm tương ứng.

Ví dụ:

• Dữ liệu vào:

3
1 2 3
1 0 2
2 1 3 

• Dữ liệu ra:

6
1 2 2
2 3 2
3 1 2

Hướng làm của e là xét tất cả các trường hợp bằng cách tạo một vòng lặp for cho nó chạy từ 1 đến m r xét xuống từng hàng dưới ạ. Nó rất dài và chạy khá lâu nên e muốn hỏi mn hướng làm tối ưu hơn ạ

[noname00 (HK boy)]

Đây là bài cặp ghép cực đại trên đồ thị 2 phía (aka cặp ghép) cơ bản, độ phức tạp O(M^2).