UVA 11733 - Airports(cpp file)

Problem Type : Graph(Minimum Spanning Tree)




#include<bits/stdc++.h>
#define MAX 100005
using namespace std;
long par[MAX],n,m,cost1;
struct node
{
    long node1;
    long node2;
    long cost;
};
node arr[MAX];
void make_set()
{
    long i;
    for(i=1; i<=n; i++)
    {
        par[i]=i;
    }
}
long find_set(long n)
{
    if(par[n]!=n)
    {
        par[n]=find_set(par[n]);
    }
    return par[n]=par[n];
}
bool comp(node x,node y)
{
    return x.cost < y.cost;
}
int main()
{
    long int i,j,len,test,ux,uy,airport,cas=0;
    long long sum;
    scanf("%ld",&test);
    while(test--)
    {
        cas++;
        cost1=0;
        scanf("%ld %ld %ld",&n,&m,&cost1);
        arr[0].node1=0;
        arr[0].node2=0;
        arr[0].cost=0;
        for(i=1; i<=m; i++)
        {
            scanf("%ld %ld %ld",&arr[i].node1,&arr[i].node2,&arr[i].cost);
        }

        sort(arr,arr+(m+1),comp);
        make_set();
        long cou=0;
        sum=0;
        airport=0;
        for(i=1; i<=m; i++)
        {
            ux=find_set(arr[i].node1);
            uy=find_set(arr[i].node2);

            if(ux!=uy)
            {
                //  printf("\n\n%ld %ld\n",arr[i].node1,arr[i].node2);
                cou++;
                par[ux]=uy;
                if(arr[i].cost>=cost1)
                {
                    sum+=cost1;
                    airport++;
                }
                else
                {
                    sum+=arr[i].cost;
                }

            }
            if(cou==n)
                break;

        }

        for(i=1; i<=n; i++)
        {
            if(par[i]==i)
            {
                sum+=cost1;
                airport++;
            }
        }
        printf("Case #%ld: %lld %ld\n",cas,sum,airport);

    }

}