1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <algorithm>
#define LL long long
#define ff first
#define ss second
#define MP make_pair
#define PB push_back
using namespace std;
const int N = 2005;
int n, x, size;
int rep[N];
pair<int, pair<int, int> >S[N*N];
int find(int w)
{
  return rep[w]==w? w: rep[w] = find(rep[w]);
}
int main()
{
  scanf("%d", &n);
  for(int i=1; i<=n; i++)
  {
    rep[i] = i;
    for(int j=i; j<=n; j++)
    {
      scanf("%d", &x);
      S[++size] = MP(x, MP(i, j+1));
    }
  }
  rep[n+1] = n+1;
  sort(S+1, S+1+size);
  LL wynik = 0;
  for(int i=1; i<=size; i++)
  {
    int a = S[i].ss.ff;
    int b = S[i].ss.ss;
    if(find(a) != find(b))
    {
      wynik += S[i].ff;
      rep[find(a)] = find(b);
    }
  }
  printf("%lld", wynik);  
  return 0;
}