Editorialist: Jingbo Shang
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.
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 <= j <= M + N) : 1 (if
j-th friend does not have
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
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.