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)

UVa 11747 - Heavy Cycle Edges

// 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
{
    int a,b,c;
    edge(int _a, int _b, int _c)
    {
        a = _a;
        b = _b;
        c = _c;
    }
    bool operator < (const edge p) const
    {
        return c < p.c;
    }
};

vector <edge> edges;
int par[26000];

int findr(int r)
{
    if(par[r]==r) return r;
    int x = findr(par[r]);
    par[r]  = x;
    return x;
}

int main()
{
    vector <int> res;
    ll n,e,wt,x,y,z;

    while(scll(n,e)==2 and n+e)
    {
        res.clear();
        edges.clear();

        REP(i,e)
        {
            scll(x,y);
            scl(z);
            edges.push_back(edge(x,y,z));
        }

        sort(ALL(edges));
        REP(i,n+1) par[i]= i;
        REP(i,SZ(edges))
        {
            int u = findr(edges[i].a),
                v = findr(edges[i].b);

            if(u!=v)
            {
                par[v] = u;
            }
            else res.push_back(edges[i].c);
        }

        if(SZ(res)==0) puts("forest");
        else
        {
            bool fl = 0;
            REP(i,SZ(res))
            {
                if(fl) putchar(' '); fl = 1;
                printf(" %d", res[i]);
            }
            puts("");
        }
    }
    return 0;
}


// ideas (unsorted)

UVa 11503 Virtual Friends

// 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;

map<string, string> par;
map<string, int> cnt;

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

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

int main()
{
    ll t,f;
    string sa, sb;
    scl(t);
    while(t--)
    {
        scl(f);
        while(f--)
        {
            cin>>sa>>sb;
            if(par[sa]=="" and !cnt[sa]) cnt[sa]=1;
            if(par[sb]=="" and !cnt[sb]) cnt[sb]=1;

            string u = findr(sa), v = findr(sb);

            if(u!=v)
            {
                par[v] = u;
                cnt[u] = cnt[u] + cnt[v];
            }
            printf("%d\n", cnt[u]);
        }
        par.clear();
        cnt.clear();
    }
    return 0;
}


/// my ideas (incomplete ideas)

UVa 11631 - Dark Roads

// 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;

#define mx 200007

struct edge
{
    int a,b,c;

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

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


ll n,e;
vector <edge> graph;
ll leader[mx];

ll presm = 0;

int findr(int r)
{
    if(r==leader[r]) return r;
   
    int x = findr(leader[r]);
    leader[r] = x;

    return x;

    //else return leader[r] = findr(leader[r]);
}

ll mst()
{
    ll mstsm = 0;

    // init
    REP(i,mx) leader[i] = i;

    //find
    REP(i,SZ(graph))
    {
        int x = findr(graph[i].a);
        int y = findr(graph[i].b);

        if(x!=y) leader[y] = x , mstsm += graph[i].c;
    }
    return mstsm;
}

ll x,y,z;

int main()
{
   // freopen("F:/fout.txt", "w", stdout);
    while(scll(n,e) and n+e)
    {
        presm = 0;

        REP(i,e)
        {
            scll(x,y); scl(z);
            graph.push_back(edge(x,y,z));
            presm += z;
        }

        sort(ALL(graph));

        ll res = presm - mst();
        printf("%lld\n", res);

        graph.clear();
    }
    return 0;
}