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
#include "stdio.h"
#include <queue>

using namespace std;

struct edge {
    int cost,x,y;

    edge& operator=(const edge& a) {
        cost=a.cost;
        x=a.x;
        y=a.y;
        return *this;
    }
};

bool operator <(const edge& e, const edge& f) {
    return e.cost > f.cost;
}

int parent[2001];
int rankk[2001];
void FUinit() {
    for(int i=0; i<2001; ++i) { parent[i]=i; rankk[i]=1; }
}

int FUfind(int v) {
    if(v!=parent[v]) parent[v]=FUfind(parent[v]);
    else return v;
    return parent[v];
}

void FUunion(int a, int b) {
    if(rankk[a]<rankk[b]) parent[a]=b;
    else {parent[b]=a; if(rankk[a]==rankk[b]) rankk[a]+=1;}
}


int main() {
    int n;
    scanf("%d",&n);

    priority_queue<edge> edges;
    for(int i=0; i<n; ++i) {
        for(int j=i+1; j<n+1; ++j) {
            edge e;
            scanf("%d",&e.cost);
            e.x=i; e.y=j;
            edges.push(e);
        }
    }

    long long tree=0;
    FUinit();
    while(!edges.empty()) {
        edge e=edges.top();
        int a=FUfind(e.x); int b=FUfind(e.y);
        if(a!=b) { tree+=e.cost; FUunion(a,b); }
        edges.pop();
    }

    printf("%lld\n",tree);
    return 0;
}