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
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <set>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

const int INF = 1 << 30;
const double EPS = 1e-12;

int t[2042];
int w[2042];

int find(int x)
{
    if(t[x]==x) return x;
    t[x]=find(t[x]);
    return t[x];
}

bool Union(int a, int b)
{
    int ra=find(a), rb=find(b);
    if(ra==rb) return false;
    if(w[ra]<=w[rb])
    {
        t[ra]=rb;
        w[rb]+=w[ra];
    }
    else
    {
        t[rb]=ra;
        w[ra]+=w[rb];
    }
    return true;
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=0; i<=n; i++)
    {
        t[i]=i;
        w[i]=1;
    }
    ll ans=0;
    vector<pair<int,pii> > v;
    for(int i=0; i<n; i++)
    {
        for(int j=i; j<n; j++)
        {
            int c;
            scanf("%d", &c);
            v.pb(mp(c,mp(i,j+1)));
        }
    }
    sort(v.begin(), v.end());
    for(int i=0; i<v.size(); i++)
    {
        int a=v[i].se.fi, b=v[i].se.se;
        if(Union(a,b))
        {
            ans+=ll(v[i].fi);
        }
    }
    printf("%lld\n", ans);
}