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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;


int n;
long long int result;
vector<pair<int, pair<short,short> > > P;


vector<short> PAR, RANK;
int FIND(int x){
    if (PAR[x]==x) return x;
    return PAR[x]=FIND(PAR[x]);
}

void UNION(int x, int y){
    x = FIND(x); y = FIND(y);
    if (RANK[x]>RANK[y]) PAR[y]=x;
    else if (RANK[x]<RANK[y]) PAR[x]=y;
    else if (x!=y){
        PAR[y]=x;
        ++RANK[x];
    }
}




int main(){

    // Wczytywanie danych
    scanf("%d", &n); P.resize(n*(n+1)/2);
    PAR.resize(n+1); RANK.resize(n+1, 0);
    for(int i=0; i<PAR.size(); ++i) PAR[i]=i;
    int k=0; for(int i=0; i<n; ++i) for(int j=0; j<n-i; ++j){
        scanf("%d", &P[k].first);
        P[k].second.first=i; P[k].second.second=i+j; ++k;
    }

    // Algorytm
    result = 0;

    vector<pair<int,int> > S(n*(n+1)/2);
    for(int i=0; i<S.size(); ++i){ S[i].first=P[i].first; S[i].second=i; }
    sort(S.begin(), S.end());


    for(int i=0; i<S.size(); ++i){
        int id = S[i].second;
        long long w = P[id].first;
        short a=FIND(P[id].second.first);
        int b=FIND(P[id].second.second+1);
        if (a==b) continue;
        result += w;
        UNION(a,b);
    }

    // Wypisywanie wyniku
    printf("%lld\n", result);
}