uva_11733.cpp

#include<bits/stdc++.h>
using namespace std ;


#define M 500000
#define pii pair<int , int >
#define mp make_pair
#define pf printf
#define sf scanf
#define sf1(a ) scanf("%d",&a)
#define pb push_back
#define sf2(a, b) scanf("%d%d",&a ,&b)
#define rep(i,n) for(i = 1 ; i<= n ;i++ )

int par[M] ,  num ;

struct vertex {
    int u  , v , w ;

};

vector <vertex >node;
bool comp(vertex p , vertex q ){
    return p.w < q.w ;

}

int find(int a ){
    if(par[a ] ==  a ) return a ;
    else return par[a ] =  find(par[a ]);

}

void make(int a , int b ){
    int u = find(a );
    int v = find(b);
    if(u != v ) par[u] =  v ;

}
int cat ;

int mst(int range){
    int i , j ,k ;
    rep(i , num + 5) par[i] = i ;
    sort(node.begin() , node.end() , comp);
    int cost =  0 , count = 0;

    for(i = 0 ; i < node.size() ; i++){
        if(find(node[i].u ) != find(node[i].v ) && node[i].w < range  )
        {
        ///*
            //*/
            make(node[i].u , node[i].v );
            cost += node[i].w ;

        }

    }
cat =  count ;
    return cost;
}


int main(){
//    freopen("in.txt","r",stdin);
  //  freopen("out.txt","w",stdout);

    int i , j ,k ,tc , print =  0;
    int n , ed , cs = 0;
    scanf("%d",&tc);
    while(tc--)
    {


        int cost ;
        scanf("%d%d%d",&n ,&ed ,&cost);
        num = n ;
        node.clear();

        while(ed--){
            vertex var ;
            scanf("%d%d%d",&var.u , &var.v , &var.w );
            node.pb(var);

        }

        k = mst(cost );

    map<int , int > m;
    int count =0;

    rep(i, num ) {
        int x =  find(i);
        if( m.find(x) == m.end()){
            m[x ] =  1;
            count++;
        }
    }

    pf("Case #%d: %d %d\n",++cs, k+ count*cost , count);

    }
    return 0 ;
}