KGP13H - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

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:

  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.