fork(2) download
copy 
  1. /**
  2. 	Template by proptit_4t41
  3. 	Applied for C++11/C++14
  4. 	Add -std=c++14 to your IDE.
  5. **/
  6.  
  7. /**
  8. 	// code written by a random fan of momocashew
  9. 	// world.execute(me);
  10. **/
  11.  
  12. /**
  13. 	To make it compatible to C++98,
  14. 	remove all tuple typedefs, unordered
  15. 	sets/maps/multisets/multimaps, and add
  16. 	a space between two '<'/'>'s when declaring
  17. 	multi-dimensional vectors (to avoid ambiguity).
  18. **/
  19.  
  20. #include <bits/stdc++.h>
  21. using namespace std;
  22.  
  23. /** -----BASIC MACROES----- **/
  24. #define endl '\n'
  25. #define i64 long long
  26. #define u64 unsigned long long
  27. #define ld long double
  28. #define pub push_back
  29. #define puf push_front
  30. #define pob pop_back
  31. #define pof pop_front
  32. #define mmap multimap
  33. #define mset multiset
  34. #define umap unordered_map
  35. #define uset unordered_set
  36. #define ummap unordered_multimap
  37. #define umset unordered_multiset
  38. #define mp make_pair
  39. #define mt make_tuple
  40. #define fi first
  41. #define se second
  42. #define REcheck cout << "RE here?\n"
  43. #define tracker1(i) cout << "working at " << i << endl;
  44. #define tracker2(i,j) cout << "working at " << i << "-" << j << endl;
  45. #define tracker3(i,j,k) cout << "working at " << i << "-" << j << "-" << k << endl;
  46. const long double PI = 3.14159265358979323846264338327950288419716939937510582097494459230;
  47. const long long MOD = 1000000007LL;
  48. const long long INF = 1e9;
  49. const long long LINF = 1e18;
  50. const long double EPS = 1e-9;
  51. const long double GOLD = ((1+sqrt(5))/2);
  52. typedef pair<i64, i64> pii;
  53. typedef pair<i64, pii> pip;
  54. typedef pair<pii, i64> ppi;
  55. typedef tuple<i64, i64> tii;
  56. typedef tuple<i64, i64, i64> tiii;
  57.  
  58. /** -----BIT CONTROLS----- **/
  59. template<class T> int getbit(T s, int i) { return (s >> 1) & 1; }
  60. template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
  61. template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
  62. template<class T> int cntbit(T s) { return __builtin_popcount(s); }
  63.  
  64. /** -----IDEAS/ALGORITHMS-----
  65.  
  66.     -------------------------- **/
  67.  
  68. /// MAIN SOLUTION STARTS HERE
  69.  
  70. /** -----CUSTOM TYPEDEFS----- **/
  71.  
  72.  
  73. /** -----GLOBAL VARIABLES----- **/
  74. //int T, cas = 0; // for multi-testcase problems
  75. i64 n, m, ans = 0; vector<pip> edge;
  76. vector<i64> chosen, parent, siz;
  77.  
  78. /** -----EXTENSIVE FUNCTIONS----- **/
  79. i64 DSUfind(i64 z) {
  80. 	while (parent[z] != z) z = parent[z];
  81. 	return parent[z];
  82. }
  83.  
  84. void DSUmerge(i64 a, i64 b) {
  85. 	i64 x = DSUfind(a), y = DSUfind(b);
  86. 	if (x == y) return;
  87. 	if (siz[x] < siz[y]) {
  88. 		parent[x] = y;
  89. 		siz[y] += siz[x];
  90. 	}
  91. 	else {
  92. 		parent[y] = x;
  93. 		siz[x] += siz[y];
  94. 	}
  95. }
  96.  
  97. /** -----COMPULSORY FUNCTIONS----- **/
  98. void VarInput() {
  99. 	//cin >> T; // for multi-testcase problems
  100. 	cin >> n >> m; edge.resize(m, mp(0LL, mp(0LL, 0LL)));
  101. 	chosen.resize(m, false);
  102. 	parent.resize(n+1); siz.resize(n+1, 1LL);
  103. 	for (i64 i=1; i<=n; i++) parent[i] = i;
  104. 	for (i64 i=0; i<m; i++) {
  105. 		i64 a, b, c; cin >> a >> b >> c;
  106. 		edge[i] = mp(c, mp(a,b));
  107. 	}
  108. 	sort(edge.begin(), edge.end());
  109. }
  110.  
  111. void ProSolve() {
  112. 	//cout << "Case " << ++cas << ": " << ans << endl; // for multi-testcase problems
  113. 	for (i64 i=0; i<m; i++) {
  114. 		pip tmp = edge[i];
  115. 		i64 x = tmp.se.fi, y = tmp.se.se;
  116. 		if (DSUfind(x) != DSUfind(y)) {
  117. 			DSUmerge(x, y); ans += tmp.fi;
  118. 		}
  119. 	}
  120. 	cout << ans;
  121. }
  122.  
  123. /** -----MAIN FUNCTION----- **/
  124. int main() {
  125. 	//freopen("FILE.INP", "r", stdin);
  126. 	//freopen("FILE.OUT", "w", stdout);
  127. 	ios_base::sync_with_stdio(0); cin.tie(NULL);
  128. 	VarInput();
  129. 	//while(T--) ProSolve(); // for multi-testcase problems
  130. 	ProSolve(); // for regular problems
  131. 	return 0;
  132. }
Success #stdin #stdout 0s 4548KB
comments (?)
stdin
copy 
6 9
1 2 1
1 3 1
2 4 1
2 3 2
2 5 1
3 5 1
3 6 1
4 5 2
5 6 2
stdout
copy 
5
https://ideone.com/uySaIj
Minimum Spanning Tree - Kruskal's Algorithm
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

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!