online advertising

Wednesday, September 24, 2014

UVa Problem 908 - Re-connecting Computer Sites

Problem:

Please find the problem here.

Solution:

This problem is a traditional use case for minimum spanning tree. The minimum cost for connecting all sites is the minimum spanning tree.

But the problem is NOT about finding a minimum spanning tree. It has already give you a minimum spanning tree and ask us to update it when given new edges.

The idea is as follow - if we add a new edge to the minimum spanning tree, we will introduce exactly one cycle, if we remove the heaviest edge from the new cycle, we will obtain a new minimum spanning tree.

The lovely fact for this new algorithm is that we don't need to process any original edges. For each new edge it is at most linear time to find out that cycle and replace the edge.

The correctness of the algorithm is non-trivial.

To start with the proof – let’s have a brief revision on the cycle property of a minimum spanning tree. Throughout the proof we assume all the edge weights are different, this make the proof easier.

Lemma 1: Cycle property
If e is an edge in a cycle C such that e is the heaviest edge, then e does not belong to the MST.

Proof: Assume the contrary such that T is a MST and e in T, let e = (u, v), T – e has two connected components, let the component U contain u and the component V contains v. Now C must have another edge f connecting U and V, T – e + f is another spanning tree, and it is lighter because e is the heaviest edge and edge weights are unique.

Lemma 2: Sufficient property for MST
Given T, a tree, and we know that for each edge e not in T, T + e has a unique cycle C, and e is the heaviest edge in C, then T must be a MST.

Proof:
By the cycle property, we already know all the edges that is the heaviest edge in some cycle must not be in any MST, so all of the edges not in T is not in MST. But MST exist, and must have the same number of edges as T does, so T is MST.

With both lemma, we can finally prove the correctness of the algorithm.

Let the new tree T’ = T – e + f.

T – e has two connected components, say P and Q.

For all edges, it either cross P and Q or not, if it does not, then the new cycle does not involve f, it was the heaviest edge in that cycle, it should still is.

If the edge g cross P and Q, then, the old cycle involve e and the new cycle involves f.

Consider the cycle formed by replacing e by the path in T’, we know

g > e, as g is the heaviest edge in the old cycle, and
g > all edge in old cycle
e, being the heaviest edge in the cycle formed in T + f, > all edge in the new path.
So g is the heaviest edge.
By lemma 2 we have all other edges are heaviest and T’ is the new MST.

More variation on updating MST can be found in Algorithms for Updating Minimum Spanning Tree.

Code:


#include "stdafx.h"

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

#include "UVa908.h"

#include <iostream>
#include <list>
#include <map>

using namespace std;

// DFS - but searching in a tree can omit the visited flags
void find_cycle(list<pair<int, int> >* adjacency_list, int last, int from, int to, int heavyFrom, int heavyTo, int maxCost, int& resultFrom, int& resultTo, int& resultCost)
{
    for (list<pair<int, int> >::iterator ni = adjacency_list[from].begin(); ni != adjacency_list[from].end(); ni++)
    {
        pair<int, int> edge = *ni;
        if (edge.first != last)
        {
            if (edge.second > maxCost)
            {
                maxCost = edge.second;
                heavyFrom = from;
                heavyTo = edge.first;
            }

            if (edge.first == to)
            {
                resultFrom = heavyFrom;
                resultTo = heavyTo;
                resultCost = maxCost;
                return;
            }
            else
            {
                find_cycle(adjacency_list, from, edge.first, to, heavyFrom, heavyTo, maxCost, resultFrom, resultTo, resultCost);
            }
        }
    }
}

int UVa908()
{
    bool first_case = true;
    while (true)
    {
        int number_of_nodes;
        cin >> number_of_nodes;
        if (cin.eof())
        {
            break;
        }

        int original_cost = 0;
        list<pair<int, int> >* adjacency_list = new list<pair<int, int> >[number_of_nodes];
        for (int i = 0; i < number_of_nodes - 1; i++)
        {
            int from, to, cost;
            cin >> from;
            cin >> to;
            cin >> cost;
            from--;
            to--;
            adjacency_list[from].push_back(pair<int, int>(to, cost));
            adjacency_list[to].push_back(pair<int, int>(from, cost));
            original_cost += cost;
        }

        int number_of_new_links;
        cin >> number_of_new_links;

        int new_cost = original_cost;
        for (int i = 0; i < number_of_new_links; i++)
        {
            int from, to, cost;
            cin >> from;
            cin >> to;
            cin >> cost;
            from--;
            to--;
            int heavyFrom;
            int heavyTo;
            int heavyCost;
            find_cycle(adjacency_list, -1, from, to, -1, -1, -1, heavyFrom, heavyTo, heavyCost);
            if (cost < heavyCost)
            {
                // Since the list need to update, make it a direct acces data structure?
                adjacency_list[heavyFrom].remove(pair<int, int>(heavyTo, heavyCost)); // Bad - this could be O(n)
                adjacency_list[heavyTo].remove(pair<int, int>(heavyFrom, heavyCost)); // Bad again
                adjacency_list[from].push_back(pair<int, int>(to, cost));
                adjacency_list[to].push_back(pair<int, int>(from, cost));
                new_cost -= heavyCost;
                new_cost += cost;
            }
        }

        int number_of_original_lines;
        cin >> number_of_original_lines;

        for (int i = 0; i < number_of_original_lines; i++)
        {
            int from, to, cost;
            cin >> from;
            cin >> to;
            cin >> cost;
            // Original line are useless;
        }

        if (first_case)
        {
            first_case = false;
        }
        else
        {
            cout << endl;
        }

        cout << original_cost << endl;
        cout << new_cost << endl;

        delete[] adjacency_list;
    }
    return 0;
}

No comments :

Post a Comment