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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <utility>
#include <set>
#include <map>
#include <queue>
using namespace std;

typedef long long LL;

#define FOR(x,b,e) for(int x=b; x<=(e); ++x)
#define REP(x,n) for(int x=0; x<(n); ++x)
#define FORD(x,b,e) for(int x=b; x>=(e); --x)
typedef pair<int,int> PII;
typedef pair<int,pair<int,int> > PIII;
#define MP make_pair 
#define MAXN 2005
#define INF 1500000007
#define ST first
#define ND second

int n;
int origin[MAXN];
int counts[MAXN];

int added[MAXN];
int mins[MAXN];
int tab[MAXN][MAXN];
int diff = 0;
priority_queue<PIII> s;
int get(int i){
  if(origin[i]!=i){
    int w = get(origin[i]);
    origin[i] = w;
    counts[w]+=counts[i];
    counts[i]=0;
    return w;
  }
  return i;
}

void add(int x){
  FOR(y,0,n)if(y!=x&&!added[y]&&mins[y]>tab[x][y]){s.push(MP(-tab[x][y],MP(x,y)));
    mins[y] = min(mins[y],tab[x][y]);
  }
}
void mergeAtoB(int a, int b){
        counts[a]+=counts[b];
        origin[b]=a;
        counts[b]=0;  
}
LL MinSpanTree(){
  //set<PIII>::iterator it;
  LL res = 0;
  for(; !s.empty()&&diff>0; ){
    PIII p = s.top();
    s.pop();
    int a = get(p.ND.ST);
    int b = get(p.ND.ND);
    if(a!=b){
      diff--;
      res-=p.ST;
      //printf("%d %d %d\n",p.ST,p.ND.ST,p.ND.ND);
      if(counts[a]>counts[b]){
        mergeAtoB(a,b);
      } else {
        mergeAtoB(b,a);
      }       
    }
    if(!added[p.ND.ST]){add(p.ND.ST); added[p.ND.ST]=1;}
    if(!added[p.ND.ND]){add(p.ND.ND); added[p.ND.ND]=1;}
  }  
  return res;
}
int main() {
  scanf("%d",&n);
  diff=n;
  REP(x,n+1)mins[x]=INF;
  REP(x,n+1){origin[x]=x; counts[x]=1;}
  REP(x,n)FOR(y,x+1,n){scanf("%d",&tab[x][y]);
    //s.push(MP(-tab[x][y],MP(x,y)));
    tab[y][x]=tab[x][y];
  }
  add(0);
  added[0]=1;
  printf("%lld\n",MinSpanTree());
  return 0;
}