Category Archives: MST

(UVa) 10600 – ACM Contest and Blackout

0
Posted on by 
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1541
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<utility>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define dd double
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
#define mp make_pair
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define fr first
#define sc second


#define FEM edges[i].sc.fr
#define SEM edges[i].sc.sc

using namespace std;

#define MAXX 102
int N, M;
vector<pair<int, paii> > edges;
vector<int>graph[MAXX];

int best, secondBest;
bool secondBestDone;
int parent[MAXX];
int cost[MAXX][MAXX];
int dir[MAXX];

int find(int u)
{
    if(parent[u] == u) return u;
    return parent[u] = find(parent[u]);
}


void bfs(int source, int target)
{
    bool visited[MAXX];

    mem(visited, false);

    visited = 1;
    queue<int>Q;
    Q.push(source);

    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();
        loop(i, SZ(graph[u]))
        {
            int v = graph[u][i];
            if(!visited[v])
            {
                visited[v] = 1;
                dir[v] = u;
                if(target == v)
                {
                    return;
                }
                Q.push(v);
            }
        }
    }
}


int cleanAndAdd(int source, int destination)
{
    int maxValue = -INF;
    while(source != destination)
    {
        //cout<<"visiting " << cost[dir]<<" cost"<<endl;
        maxValue = max(maxValue, cost[dir] );
        source = dir;
    }
    //cout<<"maxValue " <<maxValue<<endl;
    return maxValue;
}


void MST()
{
    best = 0;
    secondBestDone = false;
    secondBest = INF;


    int p, q;

    loop(i, SZ(edges))
    {
        p = find(FEM);
        q = find(SEM);

        if(p != q)
        {
            graph[ FEM ].pb(SEM);
            graph[ SEM ].pb(FEM);
            cost[SEM][FEM] = cost[FEM][SEM] = edges[i].fr;

            parent[p] = q;
            best += edges[i].fr;
        }
        else
        {
            if(!secondBestDone)
            {
                bfs(FEM, SEM);
                secondBest = min(secondBest, - cleanAndAdd(SEM, FEM) + edges[i].fr );
                if(secondBest == 0)
                    secondBestDone = 1;
            }
        }
    }

}




int main()
{
    //read();
    int p, q, w;
    int kases;
    getint(kases);

    while(kases--)
    {
        getint(N); getint(M);
        edges.clear();
        loop(i, M)
        {
            getint(p); getint(q); getint(w);
            edges.pb(mp(w, mp(p, q)));
        }
        sort(all(edges));
        for(int i=1; i<=N; i++) parent[i] = i, graph[i].clear();

        MST();
        secondBest += best;
        cout<<best<<" "<<secondBest<<endl;


    }

    return 0;
}

(UVa)10397 – Connect the Campus

0
Posted on by 
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1338
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<utility>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define dd double
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
#define mp make_pair
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define fr first
#define sc second

using namespace std;

#define MAXX 752

vector<paii> nodes;
vector<pair<double, paii> > edges;
int N, M;
int parent[MAXX];
int find(int u)
{
    if(parent[u] == u) return u;
    return parent[u] = find(parent[u]);
}

double sqr(int a)
{
    return a*a;
}


int main()
{
    int p, q;
    while(getint(N) == 1)
    {
        nodes.clear();
        edges.clear();
        loop(i, N)
        {
            getint(p); getint(q);
            nodes.pb(mp(p, q));
            parent[i] = i;
        }

        getint(M);

        loop(i, M)
        {
            getint(p); getint(q); p--; q--;
            parent[ find(p) ] = find(q);
        }

        loop(i, N)
        {
            FOR(j, i+1, N)
            {
                if(find(i) != find(j))
                {
                    edges.pb( mp( sqrt( sqr(nodes[i].fr - nodes[j].fr) + sqr(nodes[i].sc - nodes[j].sc)  ) , mp(i, j)));
                }
            }
        }


        double result = 0;
        sort(all(edges));
        loop(i, SZ(edges))
        {
            p = find(edges[i].sc.fr);
            q = find(edges[i].sc.sc);
            if( p != q)
            {
                parent[p] = q;
                result += edges[i].fr;
            }
        }

        pf("%.2lf\n", result);





    }

    return 0;
}

(UVa) 10099 – The Tourist Guide

0
Posted on by 
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1040
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<utility>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define dd double
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
#define mp make_pair
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define sc second
#define fr first

using namespace std;

#define MAXX 102
int N, R;
int parent[MAXX];
vector<pair<int, paii> >edges;
int source, destination, T;

int find(int u)
{
    if(parent[u] == u) return u;
    return parent[u] = find(parent[u]);
}

int MST()
{
    for(int i=1; i<=N; i++) parent[i] = i;

    int p, q;

    loop(i, SZ(edges))
    {
        p = find(edges[i].sc.fr);
        q = find(edges[i].sc.sc);

        if(p != q)
        {
            parent[p] = q;
        }

        if(find(source) == find(destination))
        {
            edges[i].fr--;
            return  ceil((double)T/(double)edges[i].fr);
        }
    }
}



int main()
{
    int p, q, w;
    int kaseno = 0;
    while(1)
    {
        getint(N); getint(R);
        if(N == 0 && R == 0) break;

        edges.clear();

        loop(i, R)
        {
            getint(p); getint(q); getint(w);
            edges.pb( mp(w, mp(p, q)));
        }
        sort(all(edges));
        reverse(all(edges));

        getint(source); getint(destination); getint(T);

        pf("Scenario #%d\nMinimum Number of Trips = %d\n\n", ++kaseno, MST());





    }

    return 0;
}

(UVa) 10048 – Audiophobia

0
Posted on by 
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=989
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<utility>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define dd double
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
#define mp make_pair
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define get(a, b, c) getint(a); getint(b); getint(c)
#define sc second
#define fr first

using namespace std;

#define MAXX 101
int C, S, Q;
vector< pair<int, paii> >edges;


vector<int> nodes[MAXX];
int cost[MAXX][MAXX];

int parent[MAXX];

int find(int u)
{
    if(parent[u] == u) return u;
    return parent[u] = find(parent[u]);
}

void MST()
{

    sort(all(edges));

    int p, q;


    loop(i, SZ(edges))
    {
        p = find( edges[i].sc.fr );
        q = find( edges[i].sc.sc );

        if(p != q)
        {
            parent[p] = q;
            nodes[p].pb(q);
            nodes[q].pb(p);
            cost[p][q] = edges[i].fr;
            cost[q][p] = edges[i].fr;
        }
    }

}

int dir[MAXX];

void bfs(int start, int end)
{
    int ret = -INF;
    bool visited[MAXX];
    mem(visited, 0);
    visited[start] = 1;
    queue<int> Q;
    Q.push(start);

    while( !Q.empty() )
    {
        int u = Q.front();
        loop(i, SZ(nodes[u]))
        {
            int v = nodes[u][i];
            if( !visited[v] )
            {
                visited[v] = 1;
                dir[v] = u;
                if(v == end) return;
                Q.push(v);
            }
        }
        Q.pop();
    }
}





int main()
{
    //read();
    int p, q, w;
    int kaseno = 0;
    while(1)
    {
        get(C, S, Q);
        if(C == 0 && S == 0 && Q == 0) break;

        edges.clear();
        for(int i=1; i<=C; i++) nodes[i].clear(), parent[i] = i;


        loop(i, S)
        {
            get(p, q, w);
            edges.pb( mp(w, mp(p, q) ) );
        }

        MST();

        if(kaseno) pf("\n");
        pf("Case #%d\n", ++kaseno);

        loop(i, Q)
        {
            getint(p); getint(q);
            if( find(p)  != find(q) )
            {
                pf("no path\n");
            }
            else
            {
                int ret = -INF;
                bfs(q, p);

                while(p != q)
                {
                    ret = max(ret, cost[p][ dir[p]] );
                    p = dir[p];
                }


                pf("%d\n", ret);


            }


        }




    }


    return 0;
}

(UVa) 11267 The Hire-a-Coder Business Model

0
Posted on by 
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2234
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<utility>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define dd double
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
#define mp make_pair
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define fr first
#define sc second

using namespace std;

#define MAXX 11002

vector<int>graph[MAXX];
vector< pair<int, pair<int, int> > >edges;
char color[MAXX];
int cntNodes, cntEdges;
bool possible;
int parent[MAXX];

void bfs()
{
    color[1] = 0;
    queue<int>Q;
    Q.push(1);

    int u, v;
    while( !Q.empty() )
    {
        u = Q.front(); Q.pop();
        loop(i, SZ(graph[u]))
        {
            v = graph[u][i];
            if(color[v] == color[u])
            {
                possible = false;
                return;
            }
            if(color[v] == -1)
            {
                color[v] = color[u]?0:1;
                Q.push(v);
            }

        }
    }
}


int find(int u)
{
    if(parent[u] == u)
    {
        return u;
    }
    else return parent[u] = find(parent[u]);
}



int main()
{
    int p, q, w;
    while(1)
    {
        getint(cntNodes);
        if(!cntNodes) break;


        for(int i=1; i<=cntNodes; i++)
        {
            graph[i].clear();
        }
        edges.clear();

        getint(cntEdges);

        loop(i, cntEdges)
        {
            getint(p); getint(q); getint(w);
            graph[p].pb(q);
            graph[q].pb(p);
            edges.pb( mp(w, mp(p, q)));
        }

        mem(color, -1);
        possible = 1;

        bfs();

        if(!possible)
        {
            pf("Invalid data, Idiot!\n");
        }
        else
        {
            for(int i=1; i<=cntNodes; i++) parent[i] = i;
            ll minCost = 0;
            sort(all(edges));
            loop(i, SZ(edges))
            {
                p = find(edges[i].sc.fr);
                q = find(edges[i].sc.sc);
                w = edges[i].fr;

                if(p != q || w < 0)
                {
                    minCost += w;
                    parent[p] = q;
                }
            }
            pf("%lld\n", minCost);
        }

    }

    return 0;
}

(UVa) 10034 Freckles

0
Posted on by 
/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=975
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
#define pdd pair<double, double>
#define fr first
#define sc second
#define mp make_pair

using namespace std;

#define MAXX 102

int cntPoints;
pdd points[MAXX];
int parent[MAXX];

template<typename T>
T sqr(T a)
{
    return a*a;
}

int find(int u)
{
    if(parent[u] == u)
    {
        return u;
    }
    return parent[u] = find(parent[u]);
}







int main()
{
    int kases;
    getint(kases);
    double p, q;
    double minCost;
    bool blank = false;

    while(kases--)
    {
        getint(cntPoints);
        loop(i, cntPoints)
        {
            sf("%lf %lf", &p, &q);
            points[i] = mp(p, q);
        }



        vector<pair<double, pair<int, int> > > dists;

        loop(i, cntPoints)
        {
            FOR(j, i+1, cntPoints)
            {
                dists.pb(  mp(  sqrt( sqr(points[i].fr - points[j].fr) + sqr(points[i].sc - points[j].sc)  ) , mp(i, j)   )    );
            }
        }

        sort(all(dists));
        loop(i, cntPoints)
        {
            parent[i] = i;
        }

        minCost = 0;
        int u, v;

        loop(i, SZ(dists))
        {
            u = find(dists[i].sc.fr);
            v = find(dists[i].sc.sc);

            if(u != v)
            {
                parent[u] = v;
                minCost += dists[i].fr;
            }
        }

        if(blank) pf("\n");
        else blank = true;

        pf("%.2lf\n", minCost);




    }


    return 0;
}

(UVa) 10147 – Highways

0
Posted on by 
/*
user: php
time: 0.444 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1088
*/

#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#include<algorithm>

#define getint(n) scanf("%d", &n)
#define loop(i, n) for(int i=0; i<n; i++)




using namespace std;


long long square(int a)
{
    return (long long)a * (long long)a;
}

struct plot{
    int x, y;
};

plot point[751];

struct distances{
    int from, to;
    double dist;

    void push(int a, int b)
    {
        from = a;
        to = b;
        dist = sqrt(square(point[a].x - point[b].x) + square(point[a].y - point[b].y));
    }
};



int parent[751];

distances di[281250];


int find(int townID)
{
    if(parent[townID] == townID)
    {
        return townID;
    }
    return parent[townID] = find(parent[townID]);
}


bool comp(distances a, distances b)
{
    return a.dist < b.dist;
}


int main()
{
    int kases, towns, x, y, existingHighWays, p;
    bool all_connected;
    getint(kases);
    while(kases--)
    {

        all_connected = true;
        getint(towns);

        loop(t, towns)
        {
            getint(x);
            getint(y);
            point[t].x = x;
            point[t].y = y;
        }

        loop(i, 751)
        {
            parent[i] = i;
        }

        getint(existingHighWays);

        loop(t, existingHighWays)
        {
            getint(x); //x'th highway and y'th highway are connected
            getint(y);

            x =  find(x-1);
            y = find(y-1);

            parent[x] = y;
        }

        p = 0;

        loop(i, towns)
        {
            for(int j=i+1; j<towns; j++)
            {
                if(find(i) != find(j))
                {//they are not yet connected some how
                    di[p++].push(i, j);
                }
            }
        }

        sort(di, di + p, comp);


        loop(i, p)
        {
            x = find(di[i].from);
            y = find(di[i].to);
            if(x != y)
            {
                all_connected = false;
                parent[x] = y;
                printf("%d %d\n", di[i].from+1, di[i].to+1);
            }
        }

        if(all_connected)
        {
            printf("No new highways need\n");
        }

        if(kases) printf("\n");

    }
    return 0;

}

(UVa) 544 – Heavy Cargo

0
Posted on by 
/*
user: php
time: 0.040 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=485
*/

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<map>



#define getint(a) scanf("%d", &a)
#define loop(i, n) for(int i=0; i<n; i++)

using namespace std;

map<string, string> parent;

struct DATA{
    string u, v;
    int weight;
};



bool comp(DATA a, DATA b)
{
    return a.weight > b.weight;
}



string find(string str)
{
    if(parent[str] == "")
    {
        return str;
    }
    return parent[str] = find(parent[str]);
}






int main()
{
    int number_of_cities, number_of_roads;
    string city1, city2;
    int weight;
    DATA edge;
    int minValue;
    int kaseno = 0;

    string u, v;

    vector<DATA> edgelist;

    while(true)
    {
        getint(number_of_cities);
        getint(number_of_roads);

        if(number_of_cities == 0 && number_of_roads == 0) break;

        parent.clear();
        edgelist.clear();

        loop(t, number_of_roads)
        {
            cin>>city1>>city2>>weight;
            edge.u = city1;
            edge.v = city2;
            edge.weight = weight;
            edgelist.push_back(edge);
        }

        cin>>city1>>city2;



        sort(edgelist.begin(), edgelist.end(), comp);

        minValue = 1000000;

        loop(i, number_of_roads)
        {
            u = find(edgelist[i].u);
            v = find(edgelist[i].v);
            if(u != v)
            {
                parent[u] = v;

                if(minValue > edgelist[i].weight )
                {
                    minValue = edgelist[i].weight;
                }
            }

            if(find(city1) == find(city2))
            {
                break;
            }
        }
        printf("Scenario #%d\n", ++kaseno);
        printf("%d tons\n\n", minValue);


    }
    return 0;
}