fork download
copy 
  1. /* Author : Nguyen Thanh Tung */
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define endl                 '\n'
  6. #define int                  long long
  7.  
  8. using namespace              std;
  9.  
  10. typedef pair<int, int>       ii;
  11.  
  12. const int       N            = 1e3 + 7;
  13. const long long oo           = 1e18 + 7;
  14. const long long MOD          = 1e9 + 7;
  15.  
  16. struct edges {
  17. 	int u, v, w;
  18. };
  19.  
  20. int n, m;
  21. int par[N], sz[N];
  22. vector<edges> adj;
  23.  
  24. void make_set() {
  25. 	for(int i = 0; i < n; ++i) {
  26. 		par[i] = i;
  27. 		sz[i] = 1;
  28. 	}
  29. }
  30.  
  31. int find_set(int v) {
  32. 	if(v == par[v]) {
  33. 		return v;
  34. 	}
  35. 	return par[v] = find_set(par[v]);
  36. }
  37.  
  38. bool union_sets(int a, int b) {
  39. 	a = find_set(a);
  40. 	b = find_set(b);
  41. 	if(a == b) {
  42. 		return false;
  43. 	}
  44. 	if(sz[a] < sz[b]) {
  45. 		swap(a, b);
  46. 	}
  47. 	sz[a] += sz[b];
  48. 	par[b] = a;
  49. 	return true;
  50. }
  51.  
  52. bool cmp(edges a, edges b) {
  53. 	return a.w < b.w;
  54. }
  55.  
  56. void kruskal() {
  57. 	vector<edges> mst;
  58. 	int d = 0;
  59. 	sort(adj.begin(), adj.end(), cmp);
  60. 	for(int i = 0; i < m; ++i) {
  61. 		if(mst.size() == n - 1) {
  62. 			break;
  63. 		}
  64. 		edges e = adj[i];
  65. 		if(union_sets(e.u, e.v)) {
  66. 			mst.push_back(e);
  67. 			d += e.w;
  68. 		}
  69. 	}
  70. 	if(mst.size() != n - 1) {
  71. 		cout << "Ko Lien Thong";
  72. 	}
  73. 	else {
  74. 		cout << d << endl;
  75. 		for(auto i : mst) {
  76. 			cout << i.u << " " << i.v << " " << i.w << endl;
  77. 		}
  78. 	}
  79. }
  80.  
  81. void solve() {
  82. 	cin >> n >> m;
  83. 	for(int i = 1; i <= m; ++i) {
  84. 		int u, v, w;
  85. 		cin >> u >> v >> w;
  86. 		edges tmp = {u, v, w};
  87. 		adj.push_back(tmp);
  88. 	}
  89. 	make_set();
  90. 	kruskal();
  91. }
  92.  
  93. #define TASK "code"
  94.  
  95. signed main () {
  96.     ios_base::sync_with_stdio (false);
  97.     cin.tie(nullptr), cout.tie(nullptr);
  98.     if (fopen(TASK".inp", "r")) {
  99.        freopen(TASK".inp", "r", stdin);
  100.        freopen(TASK".out", "w", stdout);
  101.     }
  102.     int T = 1;
  103.     //cin >> T;
  104.     while(T--) {
  105.         solve();    
  106.     }
  107.     return 0;
  108. }
  109.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Ko Lien Thong
https://ideone.com/85z774
language:
C++14 (gcc 8.3)
created:
1 day 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!