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

}