fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. const int MAXN = 315;
  6.  
  7. struct Edge {
  8.     int u, v, w;
  9. };
  10.  
  11. struct cmp {
  12.     bool operator() (Edge x, Edge y) {
  13.         return x.w < y.w;
  14.     }
  15. };
  16.  
  17. int N;
  18. int A[MAXN];
  19. int B[MAXN][MAXN];
  20. vector<Edge> g;
  21. bool vis[MAXN];
  22.  
  23. struct Dosu {
  24.     int par[MAXN], sz[MAXN];
  25.     void INIT() {
  26.         for (int i = 1; i <= MAXN - 1; i++) par[i] = i, sz[i] = 1;
  27.     }
  28.  
  29.     int find_set(int u) {
  30.         return (par[u] == u ? u : par[u] = find_set(par[u]));
  31.     }
  32.  
  33.     void union_set(int u, int v) {
  34.         u = find_set(u), v = find_set(v);
  35.         if (sz[u] < sz[v]) swap(u, v);
  36.         par[v] = par[u];
  37.         sz[u] += sz[v];
  38.     }
  39. } DSU;
  40.  
  41.  
  42. main() {
  43.     ios_base::sync_with_stdio(0);
  44.     cin.tie(0);
  45.     cout.tie(0);
  46.  
  47.     cin >> N;
  48.     DSU.INIT();
  49.     for (int i = 1; i <= N; i++) {
  50.         int x;
  51.         cin >> x;
  52.         g.push_back({i, N + 1, x});
  53.     }
  54.  
  55.     for (int i = 1; i <= N; i++) {
  56.         for (int j = 1; j <= N; j++) {
  57.             int w;
  58.             cin >> w;
  59.             g.push_back({i, j, w});
  60.         }
  61.     }
  62.  
  63.     sort(g.begin(), g.end(), cmp());
  64.  
  65.     int ans = 0;
  66.  
  67.     for (auto E : g) {
  68.         if (DSU.find_set(E.u) != DSU.find_set(E.v)) {
  69.             DSU.union_set(E.u, E.v);
  70.             ans += E.w;
  71.         }
  72.     }
  73.  
  74.     cout << ans;
  75. }
  76.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/59T65I
language:
C++ (gcc 8.3)
created:
30 days 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!