fork download
copy 
  1. using namespace std;
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <set>
  7. #include <cctype>
  8. #include <map>
  9. #include <cmath>
  10. #include <queue>
  11. #include <algorithm>
  12. #include <stack>
  13. #include <cctype>
  14. #include <cstring>
  15. #include <string>
  16.  
  17. #define MAX 10010
  18. #define PRIME 31
  19. #define INC 100000
  20. #define MOD 1000000007
  21. #define PI 3.1415926535897932384
  22. #define F first
  23. #define S second
  24. #define pb push_back
  25. #define mp make_pair
  26. typedef long long ll;
  27.  
  28. pair<int, int> res;
  29. int n, m, a, t;
  30. vector<pair<int, pair<int, int> > > edge;
  31. vector<int> color[MAX]; // color[i] = { Vertices colored as i }
  32. int c[MAX]; // c[i] = Color of vertex i
  33.  
  34. pair<int, int> MST(){
  35.     pair<int, int> acm = mp(0, 0);
  36.  
  37.  	// Each vertex has one color at the beginning
  38.     for(int i = 1;i <= n;i++){ c[i] = i; color[i].clear(); color[i].pb(i); }
  39.  
  40.     // Edges are sorted
  41.     sort(edge.begin(), edge.end());
  42.  
  43.     pair<int, int> aux;
  44.     for(int i = 0;i < edge.size();i++){
  45.         aux = edge[i].S;
  46.  
  47.  		// These vertices are already connected
  48.         if(c[aux.F] == c[aux.S]) continue;
  49.  
  50.  		// Merge the smaller group into the larger
  51.         if(color[c[aux.F]].size() < color[c[aux.S]].size()) swap(aux.F, aux.S);
  52.         for(int j = 0;j < color[c[aux.S]].size();j++){
  53.             if(color[c[aux.S]][j] == aux.S) continue;
  54.  
  55.             color[c[aux.F]].pb(color[c[aux.S]][j]);
  56.             c[color[c[aux.S]][j]] = c[aux.F];
  57.         }
  58.  
  59.         color[c[aux.F]].pb(aux.S);
  60.         color[c[aux.S]].clear();
  61.         c[aux.S] = c[aux.F];
  62.  
  63.         // Value of edge included in MST
  64.         acm.F += edge[i].F;
  65.     }
  66.  
  67.  	// Count the number of trees
  68.     for(int i = 1;i <= n;i++){
  69.         if(color[i].size()) acm.S++;
  70.     }
  71.  
  72.     return acm;
  73. }
  74.  
  75. int main(){
  76.     //freopen("in.txt", "r", stdin);
  77.  
  78.     cin >> t;
  79.     for(int cas = 1;cas <= t;cas++){
  80.  
  81.         cin >> n >> m >> a;
  82.         edge.clear();
  83.  
  84.         for(int x, y, v, i = 0;i < m;i++){
  85.             scanf("%d %d %d", &x, &y, &v);
  86.  
  87.  			// Only cheap edges considered as valid
  88.             if(v < a) edge.pb(mp(v, mp(x, y)));
  89.         }
  90.  
  91.         res = MST();
  92.  
  93.         printf("Case %d: %d %d\n", cas, res.F+res.S*a, res.S);
  94.     }
  95.  
  96.     return 0;
  97. }
Success #stdin #stdout 0s 3620KB
comments (?)
stdin
copy 
2
4 4 100
1 2 10
4 3 12
4 1 41
2 3 23
5 3 1000
1 2 20
4 5 40
3 2 30
stdout
copy 
Case 1: 145 1
Case 2: 2090 2
https://ideone.com/afXKPU
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!