fork(1) download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <ctime>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. int n, m;
  8. int p[1005];
  9. int r[1005];
  10. int ans;
  11. int a1[2000005], a2[2000005];
  12. int b1[2000005], b2[2000005];
  13. int c1[2000005], c2[2000005];
  14. int sa, sb, sc;
  15. int cnt;
  16.  
  17. int find(int x) {
  18. 	if (p[x] == x) return x;
  19. 	return p[x] = find(p[x]);
  20. }
  21.  
  22. bool merge(int x, int y) {
  23. 	x = find(x);
  24. 	y = find(y);
  25. 	if (x == y) return false;
  26. 	/*if (r[x] < r[y]) {
  27. 		p[x] = y;
  28. 	} else if (r[x] > r[y]) {
  29. 		p[y] = x;
  30. 	} else {
  31. 		p[x] = y;
  32. 		r[y]++;
  33. 	}*/
  34. 	/*if (rand() & 1) {
  35. 		p[x] = y;
  36. 	} else {
  37. 		p[y] = x;
  38. 	}*/
  39. 	p[x] = y;
  40. 	return true;
  41. }
  42.  
  43. int main() {
  44. 	srand((unsigned int)time(NULL));
  45. 	int test = 0;
  46. 	while (scanf("%d%d", &n, &m) != EOF) {
  47. 		test++;
  48. 		if (test != 1) printf("\n");
  49. 		printf("Instancia %d\n", test);
  50. 		for (int i = 0; i < n; i++) {
  51. 			p[i] = i;
  52. 			r[i] = 0;
  53. 		}
  54. 		sa = sb = sc = 0;
  55. 		for (int i = 0; i < m; i++) {
  56. 			int x, y, w;
  57. 			scanf("%d%d%d", &x, &y, &w);
  58. 			x--;
  59. 			y--;
  60. 			if (w == 1235) {
  61. 				a1[sa] = x;
  62. 				a2[sa] = y;
  63. 				sa++;
  64. 			} else if (w == 8977) {
  65. 				b1[sb] = x;
  66. 				b2[sb] = y;
  67. 				sb++;
  68. 			} else if (w == 10923) {
  69. 				c1[sc] = x;
  70. 				c2[sc] = y;
  71. 				sc++;
  72. 			}
  73. 		}
  74. 		ans = 0;
  75. 		cnt = n;
  76. 		for (int i = 0; i < sa /*&& cnt > 1*/; i++) {
  77. 			if (merge(a1[i], a2[i])) {
  78. 				ans += 1235;
  79. 				//cnt--;
  80. 			}
  81. 		}
  82. 		for (int i = 0; i < sb /*&& cnt > 1*/; i++) {
  83. 			if (merge(b1[i], b2[i])) {
  84. 				ans += 8977;
  85. 				//cnt--;
  86. 			}
  87. 		}
  88. 		for (int i = 0; i < sc /*&& cnt > 1*/; i++) {
  89. 			if (merge(c1[i], c2[i])) {
  90. 				ans += 10923;
  91. 				//cnt--;
  92. 			}
  93. 		}
  94. 		printf("%d\n", ans);
  95. 	}
  96. }
  97.  
Success #stdin #stdout 0.01s 49608KB
comments (?)
stdin
copy 
3 3
1 2 10923
1 3 1235
2 3 1235
3 2
1 2 1235
2 3 10923
stdout
copy 
Instancia 1
2470

Instancia 2
12158
https://ideone.com/6Z8Bb
language:
C++ (gcc 8.3)
created:
12 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!