fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define ll long long
  6.  
  7. struct edge{
  8. 	int u, v, c;
  9. };
  10.  
  11. const int maxn = 2e5 + 5;
  12. int n, m, root[maxn];
  13. vector<edge> edges;
  14.  
  15. bool cmp(edge x, edge y) {
  16. 	return x.c < y.c;
  17. }
  18.  
  19. struct dsu{
  20. 	void init(int n) {
  21. 		for (int i = 1; i <= n; ++i)
  22. 			root[i] = i;
  23. 	}
  24.  
  25. 	int find(int u) {
  26. 		return (u == root[u] ? u : root[u] = find(root[u]));
  27. 	}
  28.  
  29. 	bool join(int u, int v) {
  30. 		u = find(u); v = find(v);
  31. 		if (u == v) return false;
  32. 		root[v] = u;
  33. 		return true;
  34. 	}
  35. } dsu;
  36.  
  37. void solve() {
  38. 	cin >> n >> m;
  39. 	dsu.init(n);
  40. 	for (int i = 1; i <= m; ++i) {
  41. 		int u, v;
  42. 		cin >> u >> v;
  43. 		dsu.join(u, v);
  44. 	}
  45.  
  46. 	for (int i = 1; i <= n; ++i)
  47. 		for (int j = 1; j <= n; ++j) {
  48. 			int x; cin >> x;
  49. 			if (i == j) continue;
  50. 			if (i < j) edges.pb({i, j, x});
  51. 		}
  52.  
  53. 	ll ans = 0;
  54. 	sort(edges.begin(), edges.end(), cmp);
  55. 	for (auto e: edges) {
  56. 		if (!dsu.join(e.u, e.v)) continue;
  57. 		ans += e.c;
  58. 	}
  59.  
  60. 	cout << ans;
  61. }
  62.  
  63. signed main() {
  64.     ios_base::sync_with_stdio(0);
  65.     cin.tie(0); cout.tie(0);
  66.  
  67.     solve();
  68.  
  69.     return 0;
  70. }
  71.  
  72.  
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
5 4
1 2
2 3
3 1
4 5
0 4 5 5 8
4 0 7 6 7
5 7 0 3 10
5 6 3 0 9
8 7 10 9 0
stdout
copy 
3
https://ideone.com/I3HECB
language:
C++14 (clang 8.0)
created:
2 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!