## Friday, January 2, 2015

### UVa Problem 10779 - Collectors Problem

Problem:

Solution:

Model the graph as follow, assuming there is just 3 sticker types.

The node 0 is a master source.
The node 1, 2, 3 represents three types of stickers that Bob has
The node 4, 5, 6 represents the nodes Bob use for trading those stickers, the edge 1->4 can be used to control how many stickers Bob has to offer - Bob can offer all of the stickers he has, so it is just the number of stickers of type 1 he has.
The node 7, 8, 9 represents the unique sticker that he has after the trades, so the edge 4->7 has capacity 1, to ensure trading can work.

Now assume there is only one people Bob can trade with, call her Alice as in customary, she has three stickers, 2, 2, 3, 3, 3. So she is interested in 1 but not any others, and she can give out 1 unit of 2 and 2 unit of 3.

So to model her, we have this graph

She is interested only in 1 unit of 1 so the link from 4->11 has capacity 1. The link 11->5 has capacity 1 (as she is willing to give out 1 only) and the link 11->6 has capacity 2 (as she is willing to give out 2).

With that, just model all participants, form the graph and run maximum flow. The final flow value will be the number of unique stickers Bob has!

I have spent some good time on this problem. At the end of it when I got accepted, it is 3am at my time. Finally ...

Learn one hard learnt lesson - when modeling maximum flow with directed graph, make sure we have the reversed edge in the adjacency list, otherwise one will miss augmented path in this example.

Suppose one has chosen A-B-C-D, while it is possible to have the augmented path A-F-C-B-E-D, the missing of C-B entry in the adjacency list will make the BFS fails, so we wanted to make sure the reverse path is available when we need to do that BFS.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1720

// #define LOG

#include "UVa10779.h"

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int UVa10779_Edmonds_Karps(vector<vector<int>>& capacities, vector<vector<int>>& adjacency_list, int src, int dst);

int UVa10779()
{
int number_of_test_cases;
cin >> number_of_test_cases;
for (int test_case = 1; test_case <= number_of_test_cases; test_case++)
{
vector<vector<int>> input;
int number_of_people;
int number_of_stickers_types;
cin >> number_of_people;
cin >> number_of_stickers_types;
input.resize(number_of_people);
for (int p = 0; p < number_of_people; p++)
{
int number_of_stickers_i_have;
cin >> number_of_stickers_i_have;
input[p].resize(number_of_stickers_i_have);
for (int s = 0; s < number_of_stickers_i_have; s++)
{
int sticker_i_have;
cin >> sticker_i_have;
input[p][s] = sticker_i_have - 1; // make sticker id goes from [0, number_of_stickers_types)
}
}

// Step 2.1: Formulate the graph
// First, there is a super sink node [0]
// For each sticker, there is a source node for bob [1 ... ns]
// For each sticker, there is a trace  node for bob [1 ... ns]
// For each sticker, there is a sink   node for bob [1 ... ns]
// For each other user, there is a node
//   For each missing item from other user, there is a link from the bob trade node to the other user with capacity 1
//   For each duplicated item from other user, this is a link from the other user node to bob trade node with quantity - 1

// Step 2.2: Allocate the graph
int number_of_nodes = /* master source */ 1 +
/* master sink   */ 1 +
/* bob source    */ number_of_stickers_types +
/* bob trade     */ number_of_stickers_types +
/* bob sink      */ number_of_stickers_types +
/* other users   */ (number_of_people - 1);

vector<vector<int>> capacities;

capacities.resize(number_of_nodes);
for (int src = 0; src < number_of_nodes; src++)
{
capacities[src].resize(number_of_nodes);
for (int dst = 0; dst < number_of_nodes; dst++)
{
capacities[src][dst] = 0;
}
}

// Step 2.3: Count how many sticker per type bob have
vector<int> bob_counts;
bob_counts.resize(number_of_stickers_types);
for (int i = 0; i < number_of_stickers_types; i++)
{
bob_counts[i] = 0;
}
for (vector<int>::iterator bs = input[0].begin(); bs != input[0].end(); bs++)
{
bob_counts[*bs]++;
}

// Step 2.3: Bob sticker links
int master_source = 0;
int master_sink   = 1 + number_of_stickers_types * 3;
for (int st = 0; st < number_of_stickers_types; st++)
{
int bob_source    = st + 1;
int bob_trade     = bob_source + number_of_stickers_types;
int bob_sink      = bob_trade + number_of_stickers_types;

capacities[master_source][bob_source] = bob_counts[st];
capacities[bob_sink][master_sink] = 1;

// reverse connection could happen in residual graph
// instead of maintaining the list at that time, might as well just put
// it here now for simplicity
}

// Step 2.1: Formulate the trades
for (int p = 1; p < number_of_people; p++)
{
int people_node = master_sink + p;
vector<int> counts;
counts.resize(number_of_stickers_types);
for (int st = 0; st < number_of_stickers_types; st++)
{
counts[st] = 0;
}
for (unsigned int i = 0; i < input[p].size(); i++)
{
counts[input[p][i]]++;
}

vector<int> gives;
vector<int> takes;

for (int st = 0; st < number_of_stickers_types; st++)
{
if (counts[st] > 1)
{
gives.push_back(st);
}
else if (counts[st] == 0)
{
takes.push_back(st);
}
}

for (vector<int>::iterator ti = takes.begin(); ti != takes.end(); ti++)
{
int take = *ti;
int bob_give_node = 1 + take + number_of_stickers_types;
capacities[bob_give_node][people_node] = 1;

// reverse connection could happen in residual graph
// instead of maintaining the list at that time, might as well just put
// it here now for simplicity
}

for (vector<int>::iterator gi = gives.begin(); gi != gives.end(); gi++)
{
int give = *gi;

int give_volume = counts[give] - 1;

int bob_take_node = 1 + give + number_of_stickers_types;
capacities[people_node][bob_take_node] = give_volume;

// reverse connection could happen in residual graph
// instead of maintaining the list at that time, might as well just put
// it here now for simplicity
}
}

#ifdef LOG
cout << "digraph {" << endl;
for (int src = 0; src < number_of_nodes; src++)
{
{
int dst = *di;
cout << src << "->" << dst << " [label=\"" << capacities[src][dst] << "\"];" << endl;
}
}
cout << "}" << endl;
#endif

cout << "Case #" << test_case << ": " << UVa10779_Edmonds_Karps(capacities, adjacency_list, master_source, master_sink) << endl;
}

return 0;
}

int UVa10779_Edmonds_Karps(vector<vector<int>>& capacities, vector<vector<int>>& adjacency_list, int src, int dst)
{
int total_flow = 0;

// Step 2: Edmonds Karp's
vector<int> parents; // Allow back-tracking the path found from bfs
int number_of_nodes = capacities.size();
parents.resize(number_of_nodes); // avoid reallocation
while (true)
{
// Step 2.1: Use BFS to find an augmenting flow
queue<int> bfs_queue;
for (int n = 0; n < number_of_nodes; n++)
{
parents[n] = -1; // indicating the node is not enqueued
}

parents[src] = -2; // indicating the node is enqueued but no actual parent because this is the root
bfs_queue.push(src);
while (bfs_queue.size() > 0)
{
int current = bfs_queue.front();
bfs_queue.pop();
{
int neighbor = *ni;
if (parents[neighbor] == -1 && capacities[current][neighbor] > 0)
{
parents[neighbor] = current;
bfs_queue.push(neighbor);

if (neighbor == dst)
{
break;
}
}
}
if (parents[dst] != -1)
{
break;
}
}

if (parents[dst] == -1)
{
break;
}
else
{
// We have found an augmenting path, go through the path and find the max flow through this path
int cur = dst;
bool first = true;
int max_flow_through_path = 0;
while (true)
{
int src = parents[cur];
if (src != -2)
{
int dst = cur;
int available = capacities[src][dst];
#ifdef LOG
cout << src << "-" << available << "->" << dst << endl;
#endif
cur = parents[cur];
if (first)
{
max_flow_through_path = available;
first = false;
}
else
{
max_flow_through_path = min(max_flow_through_path, available);
}
}
else
{
break;
}
}
#ifdef LOG
cout << "flowing " << max_flow_through_path << endl << endl;
#endif
total_flow += max_flow_through_path;
// Flow the max flow through the augmenting path
cur = dst;
while (true)
{
int src = parents[cur];
if (src != -2)
{
capacities[src][cur] -= max_flow_through_path;
capacities[cur][src] += max_flow_through_path;
cur = parents[cur];
}
else
{
break;
}
}
}
}

}