fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define endl "\n"
  5.  
  6. struct edges {
  7. int a, b, weight;
  8. bool operator<(const edges& other) const {
  9. return weight < other.weight;
  10. }
  11. };
  12.  
  13. int n, k, m, par[1000009];
  14.  
  15. int find(int x) {
  16. if (par[x] != x) par[x] = find(par[x]);
  17. return par[x];
  18. }
  19.  
  20. bool join(int a, int b) {
  21. int u = find(a), v = find(b);
  22. if (u == v) return false;
  23. par[v] = u;
  24. return true;
  25. }
  26.  
  27. signed main() {
  28. ios_base::sync_with_stdio(0);
  29. cin.tie(0);
  30. cout.tie(0);
  31.  
  32. bool flag = false;
  33.  
  34. while (cin >> n) {
  35. vector<edges> edge;
  36. int ans1 = 0, ans2 = 0;
  37.  
  38. for (int i = 0; i <= n; i++) par[i] = i;
  39.  
  40. for (int i = 1; i < n; i++) {
  41. int a, b, c;
  42. cin >> a >> b >> c;
  43. ans1 += c;
  44. }
  45.  
  46. if (flag) cout << endl;
  47. flag = true;
  48.  
  49. cin >> k;
  50. for (int i = 0; i < k; i++) {
  51. int a, b, c;
  52. cin >> a >> b >> c;
  53. edge.push_back({a, b, c});
  54. }
  55.  
  56. cin >> m;
  57. for (int i = 0; i < m; i++) {
  58. int a, b, c;
  59. cin >> a >> b >> c;
  60. edge.push_back({a, b, c});
  61. }
  62.  
  63. sort(edge.begin(), edge.end());
  64.  
  65. for (int i = 0; i <= n; i++) par[i] = i;
  66.  
  67. for (auto &e : edge) {
  68. if (join(e.a, e.b)) ans2 += e.weight;
  69. }
  70.  
  71. cout << ans1 << endl << ans2 << endl;
  72. }
  73. }
  74.  
Success #stdin #stdout 0.01s 5224KB
stdin
3
1 2 1
2 3 2
1
1 3 1
2
1 2 1
2 3 2
stdout
3
2