Friday, December 31, 2010

UVA - 11228 - Transportation System

problem statement

graph algorithms, minimum spanning tree, Prim - Kruskal

In this problem you have to find several MSTs. (one MST in each state and one MST between all states)
First you have to find out which cities are in each state and then run MST for that state and
then suppose each state as a node that have railroads to other states(nodes) and run MST for the whole states that now are considered as single nodes.

I want to describe all my code here.
I have a struct to save edge i-->j and the cost :
struct edge
{
    int p, q;
    double d;
    edge ( int _p = 0, int _q = 0, double _d = 0 )
    {
        p = _p, q = _q, d = _d;
    }
    const bool operator <( const edge &two ) const
    {
        return d < two.d;
    }
};

I save my input in this datastructure :
double p[1001][2];

This function gives me the distance between point 'i' and point 'j' :
double distF( int i, int j )
{
    return sqrt( (p[i][0]-p[j][0])*(p[i][0]-p[j][0]) + (p[i][1]-p[j][1])*(p[i][1]-p[j][1])  );
}

I use disjoint set datastructure two time in my code, first to find out whether point A and point B are in the same state, how do I do that? I mark each node with par[i],
that means if for example par[2] = 3 node 2 is in the same state as 3 is and 3 is the representative of the state( or set ), and par[4] = 5 mean that node 4 is in the same state as 5 and the representative of the set is 5, then if I find an edge between node 2 and node 4, I have to merge these two sets, and I do it with function merge(int, int), and whenever I want to know whether two nodes are in the same state or not, I use function find(int) which gives me the representative of the set which my node is in and then compare find( x ) and find( y ) if they are equal they are in the same set, otherwise I have to merge them.
int find( int x )
{
    if(x == par[x])
        return x;
    return par[x] = find( par[x] );
}
void merge( int x, int y )
{
    par[ find(x) ] = find( y );
}

Now I'm ready to read input, I save input in p[i][0] and p[i][1] and then run distF( int, int ) and set the distance between point 'i' and point 'j' and then run disjoint set datastructure to find out which nodes are in the same state( as mentioned in the problem description two nodes are in the same state if the distance between them is less than 'r' ), now I have some states that I have to run MST in each state and after that I have to look at each state as single node, that have several edges to other states, so now I have to find the complete graph of the states, and then run MST for that, but between each node I have several edges( a multigraph ) so I have to choose the minimum edge between two states( suppose state 'i' has A nodes and state 'j' has B nodes, there are A*B edges between these two states that I just want the edge with minimum cost ), so I construct my graph in this way and run MST for that.
This is my MST body, "all" is a vector of edge, that all the edges of a graph are pushed back into it.
        sort( all.begin(), all.end() );
        for(int i = 0; i < n; i ++)
            par[i] = i;
        for(int k = 0; k < all.size(); k ++)
        {
            if( find( all[k].p ) == find( all[k].q ) )
                continue;
           
            railRoads += all[k].d;
            merge( all[k].p, all[k].q );
        }

No comments:

Post a Comment