Friday, January 2, 2015

UVa Problem 10779 - Collectors Problem

Problem:

Please find the problem here.

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;
        vector<vector<int>> adjacency_list;

        capacities.resize(number_of_nodes);
        adjacency_list.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_source][bob_trade] = bob_counts[st];
            capacities[bob_trade][bob_sink] = 1;
            capacities[bob_sink][master_sink] = 1;

            adjacency_list[master_source].push_back(bob_source);
            adjacency_list[bob_source].push_back(bob_trade);
            adjacency_list[bob_trade].push_back(bob_sink);
            adjacency_list[bob_sink].push_back(master_sink);

            // 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
            adjacency_list[bob_source].push_back(master_source);
            adjacency_list[bob_trade].push_back(bob_source);
            adjacency_list[bob_sink].push_back(bob_trade);
            adjacency_list[master_sink].push_back(bob_sink);
        }

        // 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;
                adjacency_list[bob_give_node].push_back(people_node);

                // 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
                adjacency_list[people_node].push_back(bob_give_node);
            }

            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;
                adjacency_list[people_node].push_back(bob_take_node);

                // 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
                adjacency_list[bob_take_node].push_back(people_node);
            }
        }

#ifdef LOG
        cout << "digraph {" << endl;
        for (int src = 0; src < number_of_nodes; src++)
        {
            for (vector<int>::iterator di = adjacency_list[src].begin(); di != adjacency_list[src].end(); di++)
            {
                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();
            for (vector<int>::iterator ni = adjacency_list[current].begin(); ni != adjacency_list[current].end(); ni++)
            {
                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;
                }
            }
        }
    }

    return total_flow;
}

No comments :

Post a Comment