fork download
copy 
  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 7652KB
comments (?)
stdin
copy 
4 3 2 3
1 2 2
2 3 2
1 2 1
2 3 100
3 4 1
stdout
copy 
204
https://ideone.com/rETr1Q
language:
C++14 (gcc 8.3)
created:
1 year 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!