hi,

im trying to solve this problem and would like to get tips in the right direction of solving this problem.

would a grapha matching solution work? or perhaps a minimum cost flow solution? or anything else?

thanks in advance.

My solution is to find really optimal matching with min-cost max-flow. Then compare it to one from input.

I solved it with negative cycle searching.

My algo have following complexity: (N+M)*(2*N*M + M*M)

It can also be a chain ending up in shelter with residue capacity.

It is also possible to make it N*M*M + M*M*M by jumping from shelter to shelter through one preselected building which grants maximum yield for that pair of shelters (hence the first N*M*M step), M*M*M is Bellman-Ford.