online advertising

Thursday, January 15, 2015

UVa Problem 11631 - Dark roads

Problem:

Please find the problem here.

Solution:

The least costly solution is the minimum spanning tree. The saving is therefore the sum of all edge weights minus the cost of the minimum spanning tree.

Instead of using the Kruskal's, I implemented the Prim's algorithm, just for learning sake. The binary heap is adopted from my own Dijkstra's algorithm - the implementation of the two problems is very similar anyway.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2678

#include "UVa11631.h"

#include <iostream>
#include <vector>
#include <map>

using namespace std;

bool UVa11631_less(vector<int>& priority_values, vector<bool>& priority_is_positive_infinity, int one, int two);
void UVa11631_bubble_down(vector<int>& priority_queue, vector<int>& priority_values, vector<bool>& priority_is_positive_infinity, vector<int>& node_index, int& queue_size, int parent_index);
int UVa11631_delete_min(vector<int>& priority_queue, vector<int>& priority_values, vector<bool>& priority_is_positive_infinity, vector<int>& node_index, int& queue_size);
void UVa11631_change_key(vector<int>& priority_queue, vector<int>& priority_values, vector<bool>& priority_is_positive_infinity, vector<int>& node_index, int& queue_size, int changed_node);
int UVa11631_Prim(vector<vector<pair<int, int>>>& adjacency_list);

int UVa11631()
{
    while (true)
    {
        // Step 1: Read input and build adjacency list
        int number_of_nodes;
        int number_of_edges;
        cin >> number_of_nodes;
        cin >> number_of_edges;
        if (number_of_nodes == 0 && number_of_edges == 0)
        {
            break;
        }

        vector<vector<pair<int, int>>> adjacency_list;
        adjacency_list.resize(number_of_nodes);
        int total_edge_weight = 0;
        for (int e = 0; e < number_of_edges; e++)
        {
            int src;
            int dst;
            int weight;
            cin >> src;
            cin >> dst;
            cin >> weight;
            adjacency_list[src].push_back(pair<int, int>(dst, weight));
            adjacency_list[dst].push_back(pair<int, int>(src, weight));
            total_edge_weight += weight;
        }


        int sum_weights = UVa11631_Prim(adjacency_list);
        cout << (total_edge_weight - sum_weights) << endl;
    }

    return 0;
}

bool UVa11631_less(vector<int>& priority_values, vector<bool>& priority_is_positive_infinity, int one, int two)
{
    if (priority_is_positive_infinity[one])
    {
        if (priority_is_positive_infinity[two])
        {
            return priority_values[one] < priority_values[two];
        }
        else
        {
            return true;
        }
    }
    else
    {
        return false;
    }
}

void UVa11631_bubble_down(vector<int>& priority_queue, vector<int>& priority_values, vector<bool>& priority_is_positive_infinity, vector<int>& node_index, int& queue_size, int parent_index)
{
    while (true)
    {
        int child2_index = (parent_index + 1) * 2;
        int child1_index = child2_index - 1;

        if (child2_index < queue_size)
        {
            int parent_value = priority_queue[parent_index];
            int child1_value = priority_queue[child1_index];
            int child2_value = priority_queue[child2_index];

            if (UVa11631_less(priority_values, priority_is_positive_infinity, child1_value, child2_value))
            {
                if (UVa11631_less(priority_values, priority_is_positive_infinity, child1_value, parent_value))
                {
                    priority_queue[parent_index] = child1_value;
                    priority_queue[child1_index] = parent_value;
                    node_index[parent_value] = child1_index;
                    node_index[child1_value] = parent_index;
                    parent_index = child1_index;
                }
                else
                {
                    break;
                }
            }
            else
            {
                if (UVa11631_less(priority_values, priority_is_positive_infinity, child2_value, parent_value))
                {
                    priority_queue[parent_index] = child2_value;
                    priority_queue[child2_index] = parent_value;
                    node_index[parent_value] = child2_index;
                    node_index[child2_value] = parent_index;
                    parent_index = child2_index;
                }
                else
                {
                    break;
                }
            }
        }
        else if (child1_index < queue_size)
        {
            int parent_value = priority_queue[parent_index];
            int child1_value = priority_queue[child1_index];

            if (UVa11631_less(priority_values, priority_is_positive_infinity, child1_value, parent_value))
            {
                priority_queue[parent_index] = child1_value;
                priority_queue[child1_index] = parent_value;
                node_index[parent_value] = child1_index;
                node_index[child1_value] = parent_index;
                parent_index = child1_index;
            }
            else
            {
                break;
            }
        }
        else
        {
            break;
        }
    }
}

int UVa11631_delete_min(vector<int>& priority_queue, vector<int>& priority_values, vector<bool>& priority_is_positive_infinity, vector<int>& node_index, int& queue_size)
{
    int u = priority_queue[0];
    node_index[u] = -1;
    if (queue_size > 1)
    {
        priority_queue[0] = priority_queue[queue_size - 1];
        priority_queue[queue_size - 1] = -1;
        node_index[priority_queue[0]] = 0;
        queue_size--;
        UVa11631_bubble_down(priority_queue, priority_values, priority_is_positive_infinity, node_index, queue_size, 0);
    }
    else
    {
        priority_queue[queue_size - 1] = -1;
        queue_size--;
    }
    return u;
}

void UVa11631_change_key(vector<int>& priority_queue, vector<int>& priority_values, vector<bool>& priority_is_positive_infinity, vector<int>& node_index, int& queue_size, int changed_node)
{
    int child_index = node_index[changed_node];
    while (child_index != 0)
    {
        int parent_index = (child_index + 1) / 2 - 1;

        int child_value = priority_queue[child_index];
        int parent_value = priority_queue[parent_index];

        if (UVa11631_less(priority_values, priority_is_positive_infinity, child_value, parent_value))
        {
            priority_queue[child_index] = parent_value;
            priority_queue[parent_index] = child_value;
            node_index[parent_value] = child_index;
            node_index[child_value] = parent_index;
            child_index = parent_index;
        }
        else
        {
            break;
        }
    }
}

int UVa11631_Prim(vector<vector<pair<int, int>>>& adjacency_list)
{
    // Step 1: Initialize the data structures
    vector<int> priority_queue;
    vector<int> node_index;
    vector<int> priority_values;
    vector<bool> priority_is_positive_infinity;
    vector<int> parents;
    int number_of_nodes = adjacency_list.size();
    priority_queue.resize(number_of_nodes);
    node_index.resize(number_of_nodes);
    priority_values.resize(number_of_nodes);
    priority_is_positive_infinity.resize(number_of_nodes);
    parents.resize(number_of_nodes);
    for (int n = 0; n < number_of_nodes; n++)
    {
        priority_queue[n] = n;
        node_index[n] = n;
        priority_values[n] = (n == 0) ? 0 : -1;
        priority_is_positive_infinity[n] = (n == 0);
        parents[n] = -1;
    }

#ifdef LOG
    cout << "digraph{" << endl;
#endif
    int sum_weights = 0;
    // Step 2: Prim's loop
    int queue_size = number_of_nodes;
    for (int e = 0; e < number_of_nodes; e++)
    {
        int src = UVa11631_delete_min(priority_queue, priority_values, priority_is_positive_infinity, node_index, queue_size);
        if (parents[src] != -1)
        {
#ifdef LOG
            cout << parents[src] << "->" << src << "[label=\"" << priority_values[src] << "\"];" << endl;
#endif
            sum_weights += priority_values[src];
        }
        for (vector<pair<int, int>>::iterator ni = adjacency_list[src].begin(); ni != adjacency_list[src].end(); ni++)
        {
            int dst = ni->first;
            if (node_index[dst] != -1) // If the node is still in the other side
            {
                int cut_cost = ni->second;
                if (!priority_is_positive_infinity[dst] || cut_cost < priority_values[dst])
                {
                    priority_is_positive_infinity[dst] = true;
                    priority_values[dst] = cut_cost;
                    parents[dst] = src;
                    UVa11631_change_key(priority_queue, priority_values, priority_is_positive_infinity, node_index, queue_size, dst);
                }
            }
        }
    }
#ifdef LOG
    cout << "}" << endl;
#endif

    return sum_weights;
}

Sunday, January 11, 2015

UVa Problem 10511 - Councilling

Problem:

Please find the problem here.

Solution:

Model the graph as follow:


All edge have capacity 1 except the ones from master_source to the parties, they should be the maximum number of persons allowed for a single party in the council.

A maximum flow of value equals to the number of clubs is possible if and only if an assignment is possible. And the assignment is given by the saturated edges.

As a side note, beware of inputs. This problem stuck me for days because I don't realize it is possible for the input to represent the same club in the club list twice. Once that duplication is removed the code is accepted.

Code:

#include "stdafx.h"

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

// #define LOG

#include "UVa10511.h"

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>

using namespace std;

int UVa10511_assign_person_number(map<string, int>& person_numbers, map<int, string>& person_namings, string person_name);
int UVa10511_assign_party_number(map<string, int>& party_numbers, map<int, string>& party_namings, string party_name);
int UVa10511_assign_club_number(map<string, int>& club_numbers, map<int, string>& club_namings, string club_name);
int UVa10511_Edmonds_Karps(vector<vector<int>>& capacities, vector<vector<int>>& adjacency_list, int src, int dst, map<int, string>& node_namings);

int UVa10511()
{
    string line;
    int number_of_test_cases;
    cin >> number_of_test_cases;
    getline(cin, line); // consume the blank link after the number of test cases    
    getline(cin, line); // consume the blank link before the first test case
    for (int test_case = 0; test_case < number_of_test_cases; test_case++)
    {
        map<string, int> person_numbers;
        map<int, string> person_namings;
        map<string, int> party_numbers;
        map<int, string> party_namings;
        map<string, int> club_numbers;
        map<int, string> club_namings;

        vector<pair<int, int>> party_members;
        map<int, set<int>> person_clubs;

        while(getline(cin, line) && line != "" && line != " ")
        {
            string person_name;
            string party_name;
            string club_name;
            stringstream sin(line);
            sin >> person_name >> party_name;

            int person_id = UVa10511_assign_person_number(person_numbers, person_namings, person_name);
            int party_id = UVa10511_assign_party_number(party_numbers, party_namings, party_name);
            party_members.push_back(pair<int, int>(party_id, person_id));
            while(sin >> club_name)
            {
                int club_id = UVa10511_assign_club_number(club_numbers, club_namings, club_name);
                /*person_clubs.insert(pair<int, int>(person_id, club_id));*/
                map<int, set<int>>::iterator probe = person_clubs.find(person_id);
                if (probe == person_clubs.end())
                {
                    person_clubs.insert(pair<int, set<int>>(person_id, set<int>()));
                }
                person_clubs[person_id].insert(club_id);
            }   
        }
        
        int number_of_parties = party_numbers.size();
        int number_of_persons = person_numbers.size();
        int number_of_clubs = club_numbers.size();

        int number_of_nodes =
            /* master source */ 1 +
            /* parties       */ number_of_parties +
            /* person        */ number_of_persons +
            /* clubs         */ number_of_clubs +
            /* master sink   */ 1;

        map<int, string> node_namings;
        int current_node = 0;
        node_namings.insert(pair<int, string>(current_node++, "master source"));
        for (int i = 0; i < number_of_parties; i++)
        {
#ifdef LOG
            cout << party_namings[i] << endl;
#endif
            node_namings.insert(pair<int, string>(current_node++, party_namings[i]));
        }
        for (int i = 0; i < number_of_persons; i++)
        {
#ifdef LOG
            cout << person_namings[i] << endl;
#endif
            node_namings.insert(pair<int, string>(current_node++, person_namings[i]));
        }
        for (int i = 0; i < number_of_clubs; i++)
        {
#ifdef LOG
            cout << club_namings[i] << endl;
#endif
            node_namings.insert(pair<int, string>(current_node++, club_namings[i]));
        }
        node_namings.insert(pair<int, string>(current_node++, "master sink"));

        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;
            }
        }

        int max_party_participants = (number_of_clubs - 1) / 2; // Floor intended, not equal or more than half

        for (int p = 0; p < number_of_parties; p++)
        {
            int party_node = p + 1;
            capacities[0][party_node] = max_party_participants;
            adjacency_list[0].push_back(party_node);
            adjacency_list[party_node].push_back(0);
        }

        int person_node_start = 1 + number_of_parties;

        for (vector<pair<int, int>>::iterator pmi = party_members.begin(); pmi != party_members.end(); pmi++)
        {
            int party_id = pmi->first;
            int person_id = pmi->second;

            int party_node = party_id + 1;
            int person_node = person_node_start + person_id;

            capacities[party_node][person_node] = 1;
            adjacency_list[party_node].push_back(person_node);
            adjacency_list[person_node].push_back(party_node);
        }

        int club_node_start = 1 + number_of_parties + number_of_persons;
        for (map<int, set<int>>::iterator pci = person_clubs.begin(); pci != person_clubs.end(); pci++)
        {
            int person_id = pci->first;
            for (set<int>::iterator ci = pci->second.begin(); ci != pci->second.end(); ci++)
            {
                int club_id = *ci;

                int person_node = person_node_start + person_id;
                int club_node = club_node_start + club_id;

                capacities[person_node][club_node] = 1;
                adjacency_list[person_node].push_back(club_node);
                adjacency_list[club_node].push_back(person_node);
            }
        }

        for (int c = 0; c < number_of_clubs; c++)
        {
            int club_node = club_node_start + c;
            capacities[club_node][number_of_nodes - 1] = 1;
            adjacency_list[club_node].push_back(number_of_nodes - 1);
            adjacency_list[number_of_nodes - 1].push_back(club_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 << node_namings[src] << "->" << node_namings[dst] << " [label=\"" << capacities[src][dst] << "\"];" << endl;
            }
        }
        cout << "}" << endl;
#endif

        int total_flow = UVa10511_Edmonds_Karps(capacities, adjacency_list, 0, number_of_nodes - 1, node_namings);

        if (test_case > 0)
        {
            cout << endl;
        }

        if (total_flow == number_of_clubs)
        {
            for (map<int, set<int>>::iterator pci = person_clubs.begin(); pci != person_clubs.end(); pci++)
            {
                int person_id = pci->first;
                for (set<int>::iterator ci = pci->second.begin(); ci != pci->second.end(); ci++)
                {
                    int club_id = *ci;

                    int person_node = person_node_start + person_id;
                    int club_node = club_node_start + club_id;

                    if (capacities[person_node][club_node] == 0)
                    {
                        cout << person_namings[person_id] << " " << club_namings[club_id] << endl;
                    }
                }
            }
        }
        else
        {
            cout << "Impossible." << endl;
        }
    }

    return 0;
}

int UVa10511_assign_party_number(map<string, int>& party_numbers, map<int, string>& party_namings, string party_name)
{
    int party_number;
    map<string, int>::iterator probe = party_numbers.find(party_name);
    if (probe == party_numbers.end())
    {
        party_number = party_numbers.size();
        party_numbers.insert(pair<string, int>(party_name, party_number));
        party_namings.insert(pair<int, string>(party_number, party_name));
    }
    else
    {
        party_number = probe->second;
    }

    return party_number;
}

int UVa10511_assign_person_number(map<string, int>& person_numbers, map<int, string>& person_namings, string person_name)
{
    int person_number;
    map<string, int>::iterator probe = person_numbers.find(person_name);
    if (probe == person_numbers.end())
    {
        person_number = person_numbers.size();
        person_numbers.insert(pair<string, int>(person_name, person_number));
        person_namings.insert(pair<int, string>(person_number, person_name));
    }
    else
    {
        person_number = probe->second;
    }

    return person_number;
}

int UVa10511_assign_club_number(map<string, int>& club_numbers, map<int, string>& club_namings, string club_name)
{
    int club_number;
    map<string, int>::iterator probe = club_numbers.find(club_name);
    if (probe == club_numbers.end())
    {
        club_number = club_numbers.size();
        club_numbers.insert(pair<string, int>(club_name, club_number));
        club_namings.insert(pair<int, string>(club_number, club_name));
    }
    else
    {
        club_number = probe->second;
    }

    return club_number;
}

int UVa10511_Edmonds_Karps(vector<vector<int>>& capacities, vector<vector<int>>& adjacency_list, int src, int dst, map<int, string>& node_namings)
{
    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 << node_namings[src] << "--" << available << "->" << node_namings[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;
}