Tags » MST

UVa 10034 - Freckles

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

typedef pair<double,double> pii;

struct edge
{
    int a,b;
    double c;

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

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

double dist(double x1, double y1, double x2, double y2)
{
    double d = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
    return d;
}

vector <pii> points;
vector<edge> edges;
map<int,int> par;

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

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

int main()
{
    bool fl = false;
    int t,n;
    double x,y;
    scanf("%d", &t);
    getchar();
    while(t--)
    {
        if(fl) printf("\n"); fl = true;

        points.clear();
        edges.clear();
        par.clear();

        scanf("%d", &n);

        REP(i,n)
        {
             scanf("%lf%lf", &x, &y);
             points.push_back(make_pair(x,y));
        }

        REP(i,n)
        {
            FOR(j,i+1,n-1)
            {

                int ii = i+1, jj = j+1;
                double dd = dist(points[i].first, points[i].second,
                                points[j].first, points[j].second);

                edges.push_back(edge(ii,jj,dd));
            }
        }

        sort(ALL(edges));

        double mstsm = 0;

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

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

        printf("%.2lf\n", mstsm);

    }
    return 0;
}
UVa

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

ll presm = 0;

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

    int x = findr(par[r]);
    par[r] = x;

    return  x;
}

ll mst()
{
    ll mstsm = 0;

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

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

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

ll x,y,z;

int main()
{
    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;
}
UVa

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;
}
… 64 more words
UVa

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;

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;
}
… 41 more words
UVa

Difficulty transitioning?

I currently live in Central Florida, a great place to live if you love warm beaches, sunshiny days, and being around veterans. With one of the highest veteran populations in the nation, it is not uncommon for a news story to appear on veterans issues. 655 more words

Veteran Woman

The Trigger Word

Trauma experiences are very real and the symptoms stemming from these events are nothing to make fun of; however, the word “trigger” has lately been mocked in the media and via many social forums . 688 more words

PTSD

Back to the basics

Having PTSD has taught me numerous and countless lessons in my life so far but the ones I have the most problems fixing or correcting seem like they should be the simplest to overcome. 686 more words

Mental Health