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

struct q
{
    int a, b, cost; 
    q() = default;
    q(int A, int B, int Cost) : a(A), b(B), cost(Cost) { }
};

inline bool operator<(const q &a, const q &b)
{
    return a.cost < b.cost;
}

int r[2001];

int Find(int k)
{
    if(r[k] != k) r[k] = Find(r[k]);
    return r[k];
}

bool Union(int a, int b)
{
    a = Find(a); b = Find(b);
    if(a == b) return false;
    r[a] = b;
    return true;
}

int main()
{
    int n, c;
    long long ans = 0;
    vector<q> vq;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
	for(int j = i; j < n; j++)
	{
	    scanf("%d", &c);
	    vq.push_back(q(i, j + 1, c));
	}
    for(int i = 0; i <= n; i++)
	r[i] = i;
    sort(vq.begin(), vq.end());
    for(const auto &x: vq)
	if(Union(x.a, x.b))
	    ans += x.cost;
    printf("%lld\n", ans);
}