UVa 1174 - IP-TV

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

struct edge
{
    string a,b;
    int c ;

    edge(string _a, string _b, int _c)
    {
        a = _a;
        b = _b;
        c = _c;
    }

    bool operator < (const edge p) const
    {
        return c < p.c;
    }
};

vector <edge> edges;
map<string,string> par;

string findr(string r)
{
    if(par[r]=="") return r;

    string x = findr(par[r]);
    par[r] = x;
    return x;
}

int main()
{
    bool fl = 0;
    int tt,n,e;
    string sa,sb;
    int c;
    scanf("%d", &tt);
    while(tt--)
    {
        par.clear();
        edges.clear();

        if(fl) printf("\n"); fl = 1;

        getchar();

        cin>>n>>e;
        REP(i,e)
        {
            cin>>sa>>sb>>c;
            edges.push_back(edge(sa,sb,c));
        }

        int mstsm = 0;

        sort(ALL(edges));

        REP(i,SZ(edges))
        {
            string u = findr(edges[i].a),
                   v = findr(edges[i].b);

            if(u!=v)
            {
                par[v] = u;
                mstsm += edges[i].c;
            }
        }

        printf("%d\n", mstsm);
    }
    return 0;
}

/// ideas (unsorted)



what did the problem want?

eu consoritium.. backbone network.. direct links...
bidirctional links..
associated cost.
the set of selected links must be
connected and include all nodes in the network.

computes the minimum cost for transmitting data to all cities

do mst and sum the edge costs

blank line b4 each data set

node (2k) edge(50k)

prnt blank line between data sets