Đây là bài toán tìm số lượng ghép đôi hoàn hảo trên đồ thị hai phía.
Với , ta không thể dùng quay lui (độ phức tạp ) vì là một số cực kỳ lớn.
Tuy nhiên, con số là dấu hiệu đặc trưng để sử dụng DP Bitmask với độ phức tạp khoảng .
2. Ý tưởng thuật toán
Trạng thái DP: Gọi dp[mask] là số cách ghép cặp cho người đàn ông đầu tiên với một tập hợp phụ nữ được biểu diễn bởi biến mask.
Giải thích Mask:mask là một số nguyên ở hệ nhị phân có bit. Nếu bit thứ của mask là , nghĩa là người phụ nữ thứ đã được ghép cặp.
Mối liên hệ: Số lượng người đàn ông đã được ghép cặp luôn bằng số lượng bit đang có trong mask. Ví dụ: nếu mask có 3 bit , nghĩa là ta đang xét việc ghép cặp cho người đàn ông thứ 3 (hoặc chuẩn bị ghép cho người thứ 4, tùy cách bạn lập chỉ số).
3. Các bước thực hiện
Khởi tạo:
Mảng dp có kích thước , tất cả bằng .
Trạng thái cơ sở: dp[0] = 1 (chưa ghép ai là 1 cách).
Duyệt qua các trạng thái:
Chạy vòng lặp mask từ đến .
Với mỗi mask, xác định số lượng người đàn ông đã được ghép: i = số bit 1 trong mask.
Xét người đàn ông tiếp theo (người thứ ). Thử ghép ông ta với tất cả những người phụ nữ mà:
Người phụ nữ chưa bị chiếm trong mask (bit thứ của mask đang là ).
Đáp án nằm ở dp[(1 << N) - 1] (tất cả các bit đều là , nghĩa là tất cả mọi người đã được ghép cặp).
4. Lưu ý khi triển khai
Độ phức tạp: . Với , số trạng thái là khoảng 2 triệu, nhân với sẽ ra khoảng 42 triệu phép tính, hoàn toàn chạy kịp trong giới hạn thời gian (thường là 1-2 giây).
Xử lý bit:
Để đếm số bit 1 trong mask: Dùng hàm có sẵn như __builtin_popcount(mask) trong C++ hoặc bin(mask).count('1') trong Python.
Để kiểm tra bit thứ có bật hay không: (mask >> j) & 1.
Bộ nhớ: Mảng dp với phần tử kiểu số nguyên (4 bytes) sẽ tốn khoảng 8MB, nằm an toàn trong giới hạn bộ nhớ thông thường (256MB).
Modulo: Đừng quên thực hiện phép chia lấy dư ở mỗi bước cộng để tránh tràn số.
