fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MX = 1e5 + 5;
  5. const int INF = 1e9 + 5;
  6. typedef signed long long ll;
  7. int set_size, p[MX], r[MX], mn_val[MX], cost[MX];
  8.  
  9. void init(int n){
  10. 	set_size = n;
  11. 	for(int i = 0; i <= n; i++){
  12. 		p[i] = i;
  13. 		r[i] = 0;
  14. 		mn_val[i] = cost[i];
  15. 	}
  16. }
  17.  
  18. int find_set(int i){
  19. 	return (p[i] == i) ? i : p[i] = find_set(p[i]);
  20. }
  21.  
  22. void union_set(int i, int j){
  23. 	int x = find_set(i), y = find_set(j);
  24. 	if(x != y){
  25. 		set_size--;
  26. 		if(r[x] > r[y]){
  27. 			p[y] = x;
  28. 			mn_val[x] = min(mn_val[x], mn_val[y]);
  29. 		}else{
  30. 			p[x] = y;
  31. 			mn_val[y] = min(mn_val[x], mn_val[y]);
  32. 			if(r[x] == r[y]) r[y]++;
  33. 		}
  34. 	}
  35. }
  36.  
  37. bool cmp(int a, int b){
  38. 	return a > b;
  39. }
  40.  
  41. int main() {
  42. 	int n, m, u, v;
  43. 	for(; scanf("%d %d", &n, &m) == 2 ;){
  44. 		vector<pair<int,int> > con;
  45.  
  46. 		for(int i = 1; i <= m; i++){
  47. 			scanf("%d %d", &u, &v);
  48. 			con.push_back(make_pair(u, v));
  49. 		}
  50.  
  51. 		for(int i = 1; i <= n; i++){
  52. 			scanf("%d", &u);
  53. 			cost[i] = u;
  54. 			if(u < 0) cost[i] = INF;
  55. 		}
  56.  
  57. 		init(n);
  58.  
  59. 		for(int i = 0; i < m; i++){
  60. 			u = con[i].first, v = con[i].second;
  61. 			union_set(u, v);
  62. 		}
  63.  
  64. 		map<int, int> mp;
  65. 		for(int i = 1; i <= n; i++){
  66. 			int par = find_set(i);
  67. 			int val = mn_val[par];
  68.  
  69. 			mp[par] = val;
  70. 		}
  71.  
  72. 		map<int, int>:: iterator it;
  73. 		bool ok = false;
  74. 		int sum = 0, mn = INF;
  75.  
  76. 		for(it = mp.begin(); it != mp.end(); it++){
  77. 			int num = it->second;
  78. 			if(num == INF) ok = true;
  79. 			sum += num;
  80. 			mn = min(mn, num);
  81. 		}
  82.  
  83. 		(ok) ? printf("-1\n") : printf("%d\n", mn * (set_size - 1) + sum - mn);
  84. 	}
  85. 	return 0;
  86. }
Success #stdin #stdout 0s 5036KB
comments (?)
stdin
copy 
3 2
1 2
2 3
1
1
1
stdout
copy 
0
https://ideone.com/oM1MVe
language:
C++14 (gcc 8.3)
created:
7 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!