Implementation of Kruskal's Minimum Spanning tree(MST) algorithm for UVa problem "11228 - Transportation system"

MST.cpp

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <stack>
#include <utility>
#include <fstream>
#include <cmath>
using namespace std;
typedef pair<int, int> ii;
const int MAXN = 1010;
struct Answer
{
    int states, roadLength, railLength;
    Answer(int s, int rl, int rl2)
    {
        states = s;
        roadLength = rl;
        railLength = rl2;
    }
};
struct UnionFind
{
    vector<int> parent, rank;
    UnionFind(int size)
    {
        ++size;
        for(int i = 0; i < size; ++i) parent.push_back(i);
        rank.assign(size, 0);
    }
    void join(int e1, int e2)
    {
        e1 = find(e1);
        e2 = find(e2);
        if(rank[e1] == rank[e2])
        {
            ++rank[e1];
            parent[e2] = e1;
        }
        else if(rank[e1] > rank[e2]) parent[e2] = e1;
        else parent[e1] = e2;
    }
    int find(int node)
    {
        if(parent[node] == node) return node;
        parent[node] = find(parent[node]);
        return parent[node];
    }
    bool sameSet(int e1, int e2)
    {
        return find(e1) == find(e2);
    }
};
struct Edge
{
    int from, to, type;
    double distance;
    Edge(int _f, int _t, double _d, int _ty)
    {
        from = _f;
        to = _t;
        type = _ty;
        distance = _d;
    }
    bool operator < (const Edge &other) const
    {
        return distance < other.distance;
    }
};
double calcDistance(const ii &a, const ii &b)
{
    double x = abs(a.first - b.first);
    double y = abs(a.second - b.second);
    return sqrt(x*x + y*y);
}
ii points[MAXN];
vector<Edge> E;
vector<Answer> answers;
void read()
{
    E.clear();
    //all ready
    int N, R;
    cin >> N >> R;
    for(int i = 0; i < N; ++i)
    {
        int x, y;
        cin >> x >> y;
        points[i] = ii(x, y);
    }
    for(int i = 0; i < N; ++i)
    {
        for(int j = i+1; j < N; ++j)
        {
            double dist = calcDistance(points[i], points[j]);
            int type = 0;
            if(dist > R) type = 1;
            Edge e = Edge(i, j, dist, type);
            E.push_back(e);
        }
    }
    sort(E.begin(), E.end());
    UnionFind S(N);
    double roadLength = 0, railLength = 0;
    int states = 1;
    int unions = 0, i = 0;
    while(i < E.size() && unions < N-1)
    {
        Edge current = E[i];
        if(!S.sameSet(E[i].from, E[i].to))
        {
            S.join(E[i].from, E[i].to);
            if(E[i].type == 0)
            {
                roadLength += E[i].distance;
            }
            else
            {
                railLength += E[i].distance;
                ++states;
            }
            ++unions;
        }
        ++i;
    }
    answers.push_back(Answer(states, (int)round(roadLength), (int)round(railLength)));
}
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for(int i = 0; i < T; ++i)
    {
        read();
    }
    for(int i = 0; i < T; ++i)
    {
        cout<<"Case #"<<i+1<<": "<<answers[i].states<<" "<<answers[i].roadLength<<" "<<answers[i].railLength<<'\n';
    }
    return 0;
}