Solutions of Brewing potion 7

Select solution language

LongvnXD Created at 1 likes

Cách dựng luồng như sau: - Đỉnh phát $S$ nối với tất cả các loại nấm $A_i$ với sức chứa $A_i$. - Mỗi loại nấm $A_i$ nối với mọi lọ $k$ mà loại $A_i$ có thể sử dụng, với sức chứa $\infty$. - Mỗi lọ $k$ nối với chính nó (hoặc tách thành hai nút $L^{\rm in}_k$ và $L^{\rm out}_k$) với sức chứa $\dfrac{C_k}{2}$. (gọi bước này là hãm). - Mỗi lọ sau khi hãm nối với tất cả các loại nấm $B_j$ có thể sử dụng, với sức chứa $\infty$. - Mỗi loại nấm $B_j$ nối với đỉnh thu $T$ với sức chứa $B_j$. Kết quả: $$ \mathrm{Ans}=2\cdot maxFlow(S,T). $$