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.

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!