fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAX = 1e3 + 10;
  4. struct Edge {
  5. 	int a, b;
  6. 	long long c;
  7. 	bool isVisited;
  8. 	Edge(): isVisited(0) {
  9. 	}
  10. 	bool operator<(const Edge& e) const {
  11. 		return c < e.c;
  12. 	}
  13. } edges[MAX * MAX];
  14. int n, m, parent[MAX];
  15. long long dp[MAX][MAX];
  16. vector<int>G[MAX];
  17. int find(int x) {
  18. 	return x == parent[x] ? x : (parent[x] = find(parent[x]));
  19. }
  20. int main() {
  21. 	cin >> n >> m;
  22. 	for(int i=0; i<m; i++) {
  23. 		cin >> edges[i].a >> edges[i].b >> edges[i].c;
  24. 	}
  25. 	sort(edges, edges+m);
  26. 	for(int i=1; i<=n; i++) {
  27. 		G[i].clear();
  28. 		G[i].push_back(i);
  29. 		parent[i] = i;
  30. 	}
  31. 	long long sum = 0;
  32. 	int current = 0;
  33. 	for(int i=0; i<m; i++) {
  34. 		if (current == n-1) break;
  35. 		int a = find(edges[i].a), b = find(edges[i].b);
  36. 		if (a == b) continue;
  37. 		current++;
  38. 		edges[i].isVisited = true;
  39. 		sum += edges[i].c;
  40. 		for(int j: G[a]) {
  41. 			for(int k: G[b]) {
  42. 				dp[i][j] = dp[b][a] = edges[i].c;
  43. 			}
  44. 		}
  45. 		parent[a] = b;
  46. 		for(int j: G[a]) {
  47. 			G[b].push_back(j);
  48. 		}
  49. 	}
  50. 	if (current != n-1) {
  51. 		cout << "-1 -1\n";
  52. 		return 0;
  53. 	}
  54. 	long long ans = LLONG_MAX;
  55. 	for(int i=0; i<m; i++) {
  56. 		if (!edges[i].isVisited) {
  57. 			ans = min(ans, sum + edges[i].c - dp[edges[i].a][edges[i].b]);
  58. 		}
  59. 	}
  60. 	if (ans > sum && ans != LLONG_MAX) {
  61. 		cout << sum << " " << ans << endl;
  62. 	} else {
  63. 		cout << sum << " " << -1 << endl;
  64. 	}
  65. }
Success #stdin #stdout 0.01s 27424KB
comments (?)
stdin
copy 
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
stdout
copy 
110 121
https://ideone.com/k1hKyN
language:
C++14 (gcc 8.3)
created:
5 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!