## Thursday, January 15, 2015

### UVa Problem 11631 - Dark roads

Problem:

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()
{
while (true)
{
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;
}

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;
total_edge_weight += weight;
}

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

{
// 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;
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];
}
{
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:

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;

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

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

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

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

for (int c = 0; c < number_of_clubs; c++)
{
int club_node = club_node_start + c;
capacities[club_node][number_of_nodes - 1] = 1;
}

#ifdef LOG
cout << "digraph {" << endl;
for (int src = 0; src < number_of_nodes; src++)
{
{
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();
{
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;
}
}
}
}

}