Uva 10779 Collector's Problem

 Uva 10779 Collector's Problem

Maximum Flow - Implemented with Dinic’s algorithm O(V^2E)

Time: 0.069

Language: CPP

The basic idea of the solution presented here is to look the vertices as cards and edges as trades. To build the graph, imagine all the possibilities of exchange of each different card. Bob can only exchange cards with his friends. Take the card with number 1. For each friend, how can i trade the cards. After that, take the card 2 and card 3 and so on. Remember that a card can only go to one friend one time. Creating a vertex LineIN and LineOUT, you can limit the exchange of one card to a specific friend. After build the possibilities, connect the cards of BOB to the respective vertices, the capacity is the number of cards. The cards are connected to sink (t) with capacity equals to 1(counting the number of different cards). Output the Maxflow.

The code here
Keep coding
Forgive my bad english