## Wednesday, December 31, 2014

### UVa Problem 10842 - Traffic Flow

Problem:

Solution:

Finding the maximum spanning tree and then find the minimum edge in it. Similar to the minimum bottleneck spanning tree problem (i.e. finding the minimum spanning tree and then find the maximum edge in it).

Code:

#include "stdafx.h"

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

#include "UVa10842.h"

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

using namespace std;

int UVa10842_find(int item, vector<int>& sets)
{
if (sets[item] < 0)
{
return item;
}
else
{
return sets[item] = UVa10842_find(sets[item], sets);
}
}

bool UVa10842_union(int item1, int item2, vector<int>& sets)
{
int set1 = UVa10842_find(item1, sets);
int set2 = UVa10842_find(item2, sets);
if (set1 != set2)
{
// Union
if (sets[set1] < sets[set2])              // set1 is larger
{
sets[set1] = sets[set1] + sets[set2]; // size increased
sets[set2] = set1;                    // union
}
else
{
sets[set2] = sets[set1] + sets[set2]; // size increased
sets[set1] = set2;                    // union
}

return true;
}
else
{
return false;
}
}

class UVa10842_Edge
{
public:
UVa10842_Edge(int _src, int _dst, int _weight) : src(_src), dst(_dst), weight(_weight) {}
int src;
int dst;
int weight;
};

class UVa10842_Edge_Less
{
public:
bool operator()(UVa10842_Edge edge1, UVa10842_Edge edge2)
{
// Note that the comparison direction is changed
return edge1.weight < edge2.weight;
}
};

int UVa10842()
{
int number_of_test_cases;
cin >> number_of_test_cases;
for (int test_case = 1; test_case <= number_of_test_cases; test_case++)
{
int number_of_nodes;
int number_of_edges;
cin >> number_of_nodes;
cin >> number_of_edges;

// Step 2.1: Kruskal's: Push all edges to priority queue
priority_queue<UVa10842_Edge, vector<UVa10842_Edge>, UVa10842_Edge_Less> edges;
for (int e = 0; e < number_of_edges; e++)
{
int src;
int dst;
int weight;
cin >> src;
cin >> dst;
cin >> weight;
edges.push(UVa10842_Edge(src, dst, weight));
}

// Step 2.2: Kruskal's 2: Setup disjoint set union find
vector<int> disjoint_sets;
disjoint_sets.resize(number_of_nodes);
for (int f = 0; f < number_of_nodes; f++)
{
disjoint_sets[f] = -1;
}

int min_cost = 0;
bool first = true;
while (num_edge_added != number_of_nodes - 1)
{
UVa10842_Edge edge = edges.top();
edges.pop();
if (UVa10842_union(edge.src, edge.dst, disjoint_sets))
{
if (first)
{
min_cost = edge.weight;
first = false;
}
else
{
min_cost = min(min_cost, edge.weight);
}