Hello Codeforces community,

I have come across this problem and I would like some help.

You are given N machines and M jobs. Each machine has a processing power P_i (integer). Each job requests a processing power P_j (integer). A job j is complete when it has a total of P_j power coming from 1 or more machines. A machine can provide some part of it's power to one or more jobs.

The bold parts above are what makes it different than the standard assignment problem.

It's guaranteed that sum of machine power = sum of job request power. Which means all jobs can be completed.

I want to minimize the number of assignments (machine, job).

Example:

Machine A (50)
Machine B (30)
Machine C (40)

Job A (70)
Job B (50)

Minimum assignments: 3
(machine A sends 50 to job B)
(machine B sends 30 to job A)
(machine C sends 40 to job A)

Is there any algorithm that solves this? (excluding brute force)

It sounds like the Generalized assignment problem, but with less restrictions. https://en.wikipedia.org/wiki/Generalized_assignment_problem

This is a bipartide graph, with integer flows and balanced.

The closest solution I got is (aside from brute force) to try a mincost-maxflow algorithm setting the imbalances and enforcing a fixed cost (say 1) to use one edge (independent of the amount of flow). However I am not sure if that works, because there is also the dual problem using potential and reduced costs. I don't know how to handle that on this problem.

Thanks!