## Tuesday, December 30, 2014

### UVa Problem 10600 - ACM Contest and Blackout

Problem:

Please find the problem here.

Solution:

The problem asks for the second best minimum spanning tree.

Second best MST T' are just MST that is not the same as the given MST T. To solve that, for each of the n - 1 edges in the T, remove it from the graph (so that it is impossible for the result to be T) and find a MST, note that the graph could be disconnected after removing edges so be careful there.

To make it run fast, we can sort the edges just once. Removing an edge from an edge list (actually, simply ignoring it in the Kruskal's loop) do not require sorting again, that will speed up implementation significantly.

Code:

#include "stdafx.h"

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

#include "UVa10600.h"

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

using namespace std;

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

bool UVa10600_union(int item1, int item2, vector<int>& sets)
{
int set1 = UVa10600_find(item1, sets);
int set2 = UVa10600_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 UVa10600_Edge
{
public:
UVa10600_Edge(int _src, int _dst, int _weight, int _edge_id) : src(_src), dst(_dst), weight(_weight), edge_id(_edge_id) { }
int src;
int dst;
int weight;
int edge_id;
};

class UVa10600_Edge_Less
{
public:
bool operator()(UVa10600_Edge edge1, UVa10600_Edge edge2)
{
return edge1.weight < edge2.weight;
}
};

int UVa10600()
{
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;

vector<UVa10600_Edge> edges;
for (int e = 0; e < number_of_edges; e++)
{
int from;
int to;
int cost;
cin >> from;
cin >> to;
cin >> cost;
edges.push_back(UVa10600_Edge(from - 1, to - 1, cost, -1));
}

// Step 2: Kruskal's: Sort the edges
sort(edges.begin(), edges.end(), UVa10600_Edge_Less());

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

// Step 3: Kruskal's: For each edge, if not create cycle, add stop when we reach the right number of connected components
int num_edge_added = 0;
int minimal_spanning_tree_cost = 0;
int current_edge_index = 0;
while (num_edge_added != number_of_nodes - 1)
{
UVa10600_Edge edge = edges[current_edge_index];
if (UVa10600_union(edge.src, edge.dst, disjoint_sets))
{
minimal_spanning_tree_cost += edge.weight;
}
current_edge_index++;
}

// Step 4: Second best
int second_best_minimal_spanning_tree_cost = 0;
bool first = true;
for (int i = 0; i < number_of_nodes - 1; i++)
{
// Step 4.1: Reset the disjoint sets
for (int p = 0; p < number_of_nodes; p++)
{
disjoint_sets[p] = -1;
}

int num_edge_added = 0;
int current_minimal_spanning_tree_cost = 0;
current_edge_index = 0;
while ((num_edge_added != number_of_nodes - 1) && (current_edge_index < number_of_edges))
{
UVa10600_Edge edge = edges[current_edge_index];

if (edge.edge_id != i)
{
if (UVa10600_union(edge.src, edge.dst, disjoint_sets))
{
current_minimal_spanning_tree_cost += edge.weight;
}
}
current_edge_index++;
}

if (num_edge_added == number_of_nodes - 1)
{
if (first)
{
second_best_minimal_spanning_tree_cost = current_minimal_spanning_tree_cost;
first = false;
}
else
{
second_best_minimal_spanning_tree_cost = min(second_best_minimal_spanning_tree_cost, current_minimal_spanning_tree_cost);
}
}
}

cout << minimal_spanning_tree_cost << " " << second_best_minimal_spanning_tree_cost << endl;
}

return 0;
}