I was able to find an LP formulation for this problem, but no idea about a polynomial algorithm solve it. Is there any one able to give me some hint? Thanks!

iC0ZSKQ42EA.jpg