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
# include <cstdio>
# include <algorithm>
using namespace std;
int u[2001];
pair <int, pair <int, int> > edges[2010000];
int find(int x)
{
	if (u[x]==x)
		return x;
	else
		return u[x]=find(u[x]);
}
void unite(int a, int b)
{
	u[find(a)]=find(b);
}
int main()
{
	int n;
	scanf("%d", &n);
	int last=0;
	for (int i=1; i<=n; ++i)
		for (int j=i; j<=n; ++j)
		{
			int x;
			scanf("%d", &x);
			edges[last]=make_pair(x, make_pair(i-1, j));
			last++;
		}
	sort(edges, edges+last);
	for (int i=0; i<=n; ++i)
		u[i]=i;
	long long res=0;
	for (int i=0; i<last; ++i)
		if (find(edges[i].second.first)!=find(edges[i].second.second))
		{
			res+=edges[i].first;
			unite(edges[i].second.first, edges[i].second.second);
		}
	printf("%lld\n", res);
}