C++Hướng dẫn bài J codewar 35 trong codelearn

Công ty Fsoft có N nhân viên nữ và M nhân viên nam chưa lập gia đình và cũng chưa có người yêu.
Ngày 14/2 tới đây, công ty muốn tặng K cặp vé xem phim cho các cặp đôi. Để đảm bảo sự kiện diễn ra thành công nhất, công ty đã làm 1 cuộc thăm dò và ghi nhận độ happy của mỗi nhân viên nữ khi đc ghép cặp với một nhân viên nam. Độ happy là 1 số nguyên dương, giá trị càng cao càng hạnh phúc.
Hãy tìm cách ghép K cặp nhân viên sao cho tổng độ hạnh phúc của các nhân viên nữ là lớn nhất. Chú ý mỗi 1 nhân viên nam và nữ chỉ được ghép vào 1 cặp đôi duy nhất.

Ví dụ:
n=2, m=3, k=2
Ma trận hạnh phúc:
1 1 4
3 1 5

thì kết quả là "{0-2;1-0}" với tổng chỉ số hạnh phúc là 7

[Thời gian chạy] 2s với C++, 12s với Java và C#, 16s với Python, Go và JavaScript.

[input] integer n
Số nhân viên nữ
n<=60

[input] integer m
Số nhân viên nam
m<=60

[input] integer k
Số vé đc phát
k<=min(n,m)

[input] array.array.integer a
Ma trận hạnh phúc, a[i][j] <= 100 thể hiện độ hạnh phúc của nhân viên nữ thứ i khi đc ghép đôi vs nhân viên nam thứ j (i=0..n-1; j=0..m-1)

[output] string
Xâu kí tự thể hiện danh sách K cặp nhân viên đc ghép đôi dưới dạng chuỗi kí tự "{i1-j1;i2-j2;....;ik-jk}" trong đó ix và jx là chỉ số của nhân viên nữ và nhân viên nam (với x= 1..k), chỉ số của nhân viên nữ và nam đều được đánh số từ 0
Trường hợp có nhiều hơn 1 kết quả, hãy in ra xâu kí tự có thứ tự từ điển nhỏ nhất

Link đề bài Problem J

Hướng dẫn

Bài này muốn full thì rất khó với beginner hoặc tầm trung do bài này áp dụng thuật cặp ghép (thuật toán đồ thị, một dạng bài của luồng)

Thuật O(m^n)

Đây là thuật đơn giản nhất mà beginner có thể làm, đơn giản là duyệt hết tất cả các trường hợp

Thuật O(n^3)

Thời gian tối đa bài này là 2 giây. Có nghĩa là thuật này vượt mức yêu cầu của đề bài, nên có thể có cách khác dễ hơn bạn có thể đóng góp bằng bình luật bên dưới. Ta áp dụng thuật Hungarian (Cặp ghép - Luồng - Đồ thị). Và ta thêm (n-k) cạnh ảo với giá trị rất lớn, và các cạnh giá trị âm nếu (2*n - k - m > 0).

Code full