fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define ld long double
  6. #define pb push_back
  7. #define fi first
  8. #define se second
  9. #define debug(x) cout << #x << " => " << x << "\n";
  10.  
  11. const long long mod = 1e9 + 7;
  12.  
  13. int n, m, p, q, ans;
  14. int a[100005], b[100005], c[100005];
  15. int x[100005], y[100005], z[100005];
  16.  
  17. vector <pair<int,pair<int,int>>> e[2];
  18. int mst[2];
  19.  
  20. int optAns, tmpAns;
  21.  
  22. struct {
  23. int par[100005], cost[100005];
  24.  
  25. int find(int u) {
  26. if(par[u] == u) return u;
  27. return par[u] = find(par[u]);
  28. }
  29.  
  30. int join(int u, int v) {
  31. u = find(u);
  32. v = find(v);
  33. if(u == v) return 0;
  34. par[u] = v;
  35. return 1;
  36. }
  37.  
  38. int join(int u, int v, int EdgeWeight) {
  39. u = find(u);
  40. v = find(v);
  41. if(u == v) return 0;
  42. par[u] = v;
  43. cost[v] = cost[v] + cost[u] + min(mst[0], EdgeWeight);
  44. tmpAns += min(mst[0], EdgeWeight);
  45. return 1;
  46. }
  47. } dsu[2];
  48.  
  49. void solve () {
  50. cin >> n >> m >> p >> q;
  51.  
  52. // dalam negeri
  53. for(int i = 1; i <= p; i++) {
  54. cin >> a[i] >> b[i] >> c[i];
  55. ans += n * c[i];
  56.  
  57. e[1].pb({c[i], {a[i], b[i]}});
  58. }
  59.  
  60. // luar negeri
  61. for(int i = 1; i <= q; i++) {
  62. cin >> x[i] >> y[i] >> z[i];
  63. ans += m * z[i];
  64.  
  65. e[0].pb({z[i], {x[i], y[i]}});
  66. }
  67.  
  68. for(int i = 1; i <= n; i++) {
  69. dsu[0].par[i] = i;
  70. }
  71.  
  72. sort(e[0].begin(), e[0].end());
  73. sort(e[1].begin(), e[1].end());
  74.  
  75. for(auto i : e[0]) {
  76. int u = i.se.fi, v = i.se.se, w = i.fi;
  77. if(dsu[0].join(u, v)) {
  78. mst[0] += w;
  79. }
  80. }
  81.  
  82. for(int i = 1; i <= m; i++) {
  83. dsu[1].par[i] = i;
  84. }
  85.  
  86. for(auto i : e[1]) {
  87. int u = i.se.fi, v = i.se.se, w = i.fi;
  88. if(dsu[1].join(u, v)) {
  89. mst[1] += w;
  90. }
  91. }
  92.  
  93. for(int i = 1; i <= m; i++) {
  94. dsu[1].par[i] = i;
  95. }
  96.  
  97. tmpAns = 0;
  98. tmpAns += mst[1] + mst[0];
  99.  
  100. for(auto i : e[1]) {
  101. int u = i.se.fi, v = i.se.se, w = i.fi * (n - 1);
  102. dsu[1].join(u, v, w);
  103. }
  104.  
  105. // debug(mst[0]);
  106. // debug(mst[1]);
  107.  
  108. // debug(tmpAns);
  109. // debug(ans);
  110.  
  111. ans = max(0ll, ans - tmpAns);
  112. cout << ans << "\n";
  113. }
  114.  
  115. signed main () {
  116. ios_base::sync_with_stdio(0);
  117. cin.tie(0);
  118. cout.tie(0);
  119. solve ();
  120. }
Success #stdin #stdout 0.01s 9812KB
stdin
4 2 1 3
1 2 2
1 2 1
2 3 100
3 4 1
stdout
102