1769. Which Jobs To Take and Which Tools To Buy

There are nl jobs and nr tools. Job i pays r when done. Tool j costs c to buy, once, and may then be used by any number of jobs. m lines each say that a particular job NEEDS a particular tool: the job cannot be done unless that tool has been bought.

Choose which jobs to do. Print the largest possible profit, meaning total pay minus total tool cost. Doing nothing is allowed, so the answer is never negative.

jobs: job1 pays 10, job2 pays 9 tools: tool1 costs 6, tool2 costs 7 needs: job1-tool1, job2-tool1, job2-tool2 -> 6

Every option, in full:

nothing 0 job1 only 10 - 6 = 4 job2 only 9 - (6 + 7) = -4 both 19 - (6 + 7) = 6

Job 2 alone is a loss, and doing it alongside job 1 is still the best plan, because tool 1 is then already paid for. That is the whole subject: a job's worth depends on which other jobs you take.

## What most people try first

Take every job whose own pay exceeds the cost of the tools it needs. That misses the entire point, which is SHARING: two jobs each paying 4 and both needing one tool costing 6 are each unprofitable alone and worth 2 together.

The opposite error is to take every job whose pay exceeds its share of the tools, which has no well-defined meaning once a tool is shared by three jobs with different pay.

The exhaustive version is every subset of jobs, 2^nl. That is what this problem's oracle does, on at most five jobs.

## The method, as a minimum cut

Let R be the total pay of ALL jobs. Build a network:

S -> job i capacity r(i) tool j -> T capacity c(j) job i -> tool j capacity INF, for every need

Then the answer is R minus the minimum cut, which by problem 1756's equality is R minus the maximum flow.

## Why

A cut puts each node on the source side or the sink side. Read the source side as "the jobs I am doing and the tools I am buying". Then:

a job NOT done -> its S arc is cut, paying r(i) a tool BOUGHT -> its T arc is cut, paying c(j) a job done needing an unbought tool -> an INF arc is cut

The last line is why INF is there: it makes that combination infinitely expensive, so every finite cut corresponds to a selection where every needed tool really is bought. For such a selection the cut costs

(R - pay of the jobs done) + (cost of the tools bought) = R - profit

So minimising the cut maximises the profit, and the maximum profit is R - mincut. Doing nothing is the cut that pays R and buys nothing, so the answer is at least 0 automatically and no special case is needed.

## How large INF has to be

Derive it. No finite cut ever exceeds R + (total tool cost), since cutting every S arc and every T arc is a cut, so one more than that sum is enough:

INF = r(1) + ... + r(nl) + c(1) + ... + c(nr) + 1

At nl = nr = 300 and values up to 10^9 that is 6 * 10^11, which is past the 2147483647 a signed 32-bit integer holds, so INF and the flow total both need 64 bits. A 32-bit "infinity" becomes a real capacity and quietly caps the cut, which looks like a subtly wrong answer rather than a crash.

## Cost

The network has nl + nr + 2 nodes and nl + nr + m arcs. Edmonds-Karp is O(V * E * E), about 602 * 3600 * 3600, which is too pessimistic to quote usefully; in practice the flow is bounded by R and each round is O(E), and at these limits it finishes well inside time. The important bound is that the number of rounds is at most V * E / 2, which is 1.1 * 10^6.

Constraints - `1 ≤ nl ≤ 300` - `1 ≤ nr ≤ 300` - `0 ≤ m ≤ 3000` - `1 ≤ u ≤ nl` and `1 ≤ v ≤ nr` - `1 ≤ r ≤ 1000000000` for every job - `1 ≤ c ≤ 1000000000` for every tool - a tool bought once may be used by any number of jobs - the same need may be listed more than once, and a job may need no tool at all, so the graph may be disconnected