Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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 = 0 ; 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 mst(){
- int i , j ,k ;
- rep(i , num + 5) par[i] = i ;
- sort(node.begin() , node.end() , comp);
- int cost = 0;
- for(i = 0 ; i < node.size() ; i++){
- if(find(node[i].u ) != find(node[i].v ) )
- {
- make(node[i].u , node[i].v );
- cost += node[i].w ;
- }
- }
- 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();
- map<int , int > m;
- int count = 0;
- for(i= 1 ; i<= num ;i++){
- 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 ;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement