fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. #include <string>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9.  
  10. struct edge {
  11. 	int x;
  12. 	int y;
  13. 	int cost;
  14. 	edge(int a, int b, int c) {
  15. 		x = a;
  16. 		y = b;
  17. 		cost = c;
  18. 	}
  19. 	bool operator<(edge &other) {
  20. 		if (this->cost < other.cost) {
  21. 			return true;
  22. 		}
  23. 		else {
  24. 			return false;
  25. 		}
  26. 	}
  27. };
  28.  
  29.  
  30. vector<edge> kv;
  31. int parent[100001];
  32.  
  33. int get_parent(int x) {
  34. 	if (parent[x] == x) {
  35. 		return parent[x];
  36. 	}
  37. 	else {
  38. 		parent[x] = get_parent(parent[x]);
  39. 		return parent[x];
  40. 	}
  41. }
  42.  
  43. void Union(int a, int b) {
  44. 	a = get_parent(a);
  45. 	b = get_parent(b);
  46. 	if (a < b) {
  47. 		parent[b] = a;
  48. 	}
  49. 	else {
  50. 		parent[a] = b;
  51. 	}
  52. }
  53.  
  54. int n, m;
  55. int sch[1001] = { 0, }; // 0 남자 , 1 여자
  56. int main() {
  57.  
  58. 	ios_base::sync_with_stdio(false); 
  59. 	cin.tie(nullptr); 
  60. 	cout.tie(nullptr);
  61.  
  62. 	cin >> n >> m;
  63. 	for (int i = 1; i <= n; i++) {
  64. 		parent[i] = i;
  65. 		string str;
  66. 		cin >> str;
  67. 		if (str == "M") {
  68. 			sch[i] = 0;
  69. 		}
  70. 		else {
  71. 			sch[i] = 1;
  72. 		}
  73. 	}
  74.  
  75. 	for (int i = 0; i < m; i++) {
  76. 		int a, b, c;
  77. 		cin >> a >> b >> c;
  78. 		if (sch[a] != sch[b]) {
  79. 			edge e(a, b, c);
  80. 			kv.push_back(e);
  81. 		}
  82. 	}
  83. 	sort(kv.begin(), kv.end());
  84. 	int answer = 0;
  85.  
  86. 	for (int i = 0; i < m; i++) {
  87. 		int x = kv[i].x;
  88. 		int y = kv[i].y;
  89.  
  90. 		int a = get_parent(x);
  91. 		int b = get_parent(y);
  92. 		int cost = kv[i].cost;
  93.  
  94. 		if (a != b) {
  95. 			Union(a, b);
  96. 			answer += cost;
  97. 		}
  98. 	}
  99. 	for (int i = 1; i <= n; i++) {
  100. 		if (get_parent(i) != 1) {
  101. 			cout << -1;
  102. 			return 0;
  103. 		}
  104. 	}
  105.  
  106. 	cout << answer;
  107. }
Success #stdin #stdout 0.01s 5544KB
comments (?)
stdin
copy 
5 7
M W W W M
1 2 12
1 3 10
4 2 5
5 2 5
2 5 10
3 4 3
5 4 7
stdout
copy 
34
https://ideone.com/Zvk62L
language:
C++14 (gcc 8.3)
created:
2 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!