 # KGP13H - Editorial

Editorialist: Jingbo Shang

Medium-Hard

Max Flow

### PROBLEM:

There are M objects and N friends. Given a (N+1) * M matrix which indicates how many objects everyone has. The exchange rule is that I can use an object ,which my friend X doesn’t have, to exchange for another object he has more than one. The question is to gather as many as possible different objects.

### EXPLANATION:

This problem is a same problem as UVA 10779 Collectors Problem. The solution is mainly about max flow.

Let’s build a network as following. First of all, the node part. The network has N+M+1 nodes:

1. 0-th node represents me (the source node).
2. 1-st to M-th nodes represent M different objects available.
3. (M+1)-th (M+N)-th nodes represent N different friends of me.
4. (M+N+1)-th node represents dummy sink node.

And then, here comes the arcs:

1. 0 to i (1 <= i <= M) : Number of i-th object that I have.
2. i (1 <= i <= M) to j (M +
1 <= j <= M + N)
: 1 (if
j-th friend does not have
i-th object).
3. j (M + 1 <= j <= M + N) to
i (1 <= i <= M) : (Number of
i-th object that j
has) - 1. (if j-th friend
does have i-th object more
than 1)
4. i (1 <= i <= M) to
M+N+1 : 1.

In this network, any augment path from source to sink corresponds to an exchange plan to get a different object. Therefore, the max flow in this network is the maximum different objects I can have.