This is my homework on the programming course. Now let’s examine the topic ’Maximum Flow Problem’. The task is to be solved by using this technique. Below I explain the task and what I am trying to do to solve it. Please check my approach and see if it is correct. If not, what is my mistake?
This is the original task I am trying to solve:
Companies with N workers move from one place to another. Each worker has several gold bars to bring along while moving. The worker can give some of his bars to another worker, but only if he trusts the other worker. And the other worker can also give this bar to the other worker whom he trusts. What is the minimum possible number of bars that the most stressed worker should bring if he optimally distributes bars?
Entry for the task:
In the first line we get 2 numbers N and K (1 ≤ N ≤ 100, 0 ≤ K ≤ N (N-1) / 2) – number of employees in the company and number of trust pairs. Next N numbers v_i (1 ≤ v_i ≤ 10 ^ 6) – number of bards that each worker initially has. In each of the next K lines, we have 2 numbers a and b, which represent the fact that workers are a trust worker b to carry their poles.
My guess about the solutions:
I suspect that the complexity of the expected solution is O (N ^ 2 * k * log v) where k is the maximum number of v_i. In this solution, O (N ^ 2 * k) is the complexity of the Dinic algorithm.
Let us check if it is possible that the solution is m. We can start with the value m = k / 2. In that case, the worker can either accept gold bars from other workers if v_i < m or give bars to other workers if v_i > m.
The task could only have a solution if the sum of the items that workers should give so as not to carry more than m bars is less than the number of items that workers can take. It means that
$$
sum_ {i = 1} ^ N m – v_i geq 0
$$
My approach is this:
- Create virtual source and sink nodes in the diagram.
- Connect the source node to the worker if v_i> m and set the capacity of the edge to m – v_i.
- Connect the worker to the sink node if v_i <m and set the capacity of the edge to v_i – m.
- Connect worker a to worker b if a trusts b. But how big should the capacity of the edge be? Maybe set to "unlimited"?
Check that the maximum flow is the sum of the capacity of all edges coming from the source. In this case, any additional gold workers who should give away to have no more than m bars would and should be given to some workers who can carry it and still have less than m bars in their hands.
Please check my approach. I cannot prove that it should work. But I have a feeling that it could be fine.
