Hỏi bài QBFLOWER

https://vn.spoj.pl/problems/QBFLOWER/
Mọi người cho mình hỏi bài này ý tưởng như thế nào vậy ? đọc đề rồi mà chẳng có tia sáng nào cả

Tao có ý thế này.
Giả sử, ta tìm được tập hợp nhiều bạn nam nhất có thể sao cho không có 2 bạn nam cùng nào muốn tăng hoa cho một bạn nữ nào đó, gọi số nam đó là x.
Số nữ còn lại sẽ là m-x/2.
Mỗi ng trong số những người còn lại này sẽ được tặng hoa bởi 1 và chỉ 1 ngừơi nam, những người nam này là những ng có 1 trong 2 ng nữ mà họ thích đã được tăng bởi 1 trong x thằng phía trên (Vì không còn ng nam nào mà 2 ng họ thích đều chưa có hoa), và luôn luôn tồn tại một người nam như vậy vì bài toán luôn có một lời giải nào đó.
Vậy trở về việc tìm "tập độc lập cực đại" trên một đồ thị gồm có các đỉnh là 1000 bạn nam, trong đó 2 bạn nam có cạnh nối nếu cùng thích ít nhất 1ng nữ.

nhin vao ngai dich qua
Anh co the noi so so qua de khong

Nham roi
tuong noi bai moi

lenhhoxung đã viết:

Tao có ý thế này.
Giả sử, ta tìm được tập hợp nhiều bạn nam nhất có thể sao cho không có 2 bạn nam cùng nào muốn tăng hoa cho một bạn nữ nào đó, gọi số nam đó là x.
Số nữ còn lại sẽ là m-x/2.
Mỗi ng trong số những người còn lại này sẽ được tặng hoa bởi 1 và chỉ 1 ngừơi nam, những người nam này là những ng có 1 trong 2 ng nữ mà họ thích đã được tăng bởi 1 trong x thằng phía trên (Vì không còn ng nam nào mà 2 ng họ thích đều chưa có hoa), và luôn luôn tồn tại một người nam như vậy vì bài toán luôn có một lời giải nào đó.
Vậy trở về việc tìm "tập độc lập cực đại" trên một đồ thị gồm có các đỉnh là 1000 bạn nam, trong đó 2 bạn nam có cạnh nối nếu cùng thích ít nhất 1ng nữ.

Ý tưởng ở trên mang tính đột phá ,đánh dấu sự trưởng thành của diển đàn BK-ACM của chúng ta
với ý tưởng của cu Xuân thì bài này có thể mở rộng thành trường hợp 1 bạn Nam muốn tặng hoa cho K bạn nữ (K>=1)
( vì theo ý tưởng ở trên thì số bạn nam phải chọn là : m - (k-1)*x (với x là số phần tử của tập độc lập các bạn nam) --> chỉ cần tìm x sao cho x cực đại ).
Vấn đề cuối cùng ở đây là : có ai biết cài thành thạo luồng hoặc cặp ghép để hiện thực ý tưởng trên ko ? ( đơn giản vì mình chưa code rành cặp ghép với luồng )

Bài này vốn là bài PARTY trên IOICAMP. Trên đấy thấy có thuật toán như sau

Code:

Gọi 2 đỉnh nối với đỉnh Xi là Yi1 và Yi2.
Tại bước tìm cặp ghép ,
xuất phát từ 1 đỉnh thuộc Y chưa ghép, gọi là Yi, với các đỉnh Xk có
cạnh nối với nó, nếu coi Yi=Yk1 , ta xét đỉnh Yk2.
Nếu Yk2 chưa ghép ,bước tìm đường tăng kết thúc tại Yk2.
Nếu Yk2 đã ghép, gọi đỉnh ghép với nó là Xj, nếu coi Yk2=Yj1 thì ta bỏ Yj2 vào queue
Như
vậy đường tăng cặp ghép là 1 đường xuất phát từ 1 đỉnh thuộc Y chưa
ghép, qua liền 2 cạnh chưa ghép, rồi lại đã ghép, rồi lại chưa ghép
(đều là 2 cạnh) ,và kết thúc tại 1 đỉnh cũng thuộc Y chưa ghép

Cuối cùng sẽ đưa bài toán về tìm bộ ghép cực đại (sửa đổi chút ít) tuy nhiên em cũng chưa thử cài.

Em thấy team HCMUT đã có người AC bài này rồi, có thể share source code cho mọi người tham khảo không?