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
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

typedef long long int ll;

vector<pair<int, pair<int, int> > > v;

int n;

int fut[2005];
int fuf(int w) { return (fut[w] == w) ? w : (fut[w] = fuf(fut[w])); }
inline void fuu(int u, int v) { fut[fuf(u)] = fuf(v); }

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		fut[i] = i;
		for(int j = i; j <= n; j++)
		{
			int c;
			scanf("%d", &c);
			v.push_back(make_pair(c, make_pair(i, j)));
		}
	}
	sort(v.begin(), v.end());
	ll koszt = 0LL;
	for(int i = 0; i < (int) v.size(); i++)
	{
		if(fuf(v[i].second.first - 1) == fuf(v[i].second.second))
			continue;
		koszt += v[i].first;
		fuu(v[i].second.first - 1, v[i].second.second);
	}
	printf("%lld\n", koszt);
	return 0;
}