### PROBLEM LINK:

**Editorialist:** Jingbo Shang

### DIFFICULTY:

Medium-Hard

### PREREQUISITES:

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:

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

And then, here comes the arcs:

- 0 to
**i (1 <= i <= M)**: Number of i-th object that I have. -
**i (1 <= i <= M)**to**j (M +**: 1 (if

1 <= j <= M + N)

**j**-th friend does not have

**i**-th object). -
**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) -
**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.