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
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAKS 2048
#define f first
#define s second
#define mp make_pair
using namespace std;
typedef long long int lld;
vector< pair<lld, pair<int,int> > > v;
int n;
int ojciec[MAKS];
int ranga[MAKS];
int znajdz(int x)
{
	if(x==ojciec[x])return x;
	ojciec[x]=znajdz(ojciec[x]);
	return ojciec[x];
}
bool zlacz(int a, int b)
{
	int oa=znajdz(a); int ob=znajdz(b);
	if(oa==ob)return false;
	if(ranga[oa]<ranga[ob])ojciec[oa]=ob;
	else
	{
		ojciec[ob]=oa;
		if(ranga[oa]==ranga[ob])ranga[oa]++;
	}
	return true;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            lld x;
            scanf("%lld",&x);
            v.push_back(mp(x,mp(i-1,j)));
        }
    }
    sort(v.begin(),v.end());
    
    for(int i=0;i<=n;i++)ojciec[i]=i;
    
    lld wyn=0;
    for(int i=0;i<v.size();i++)
    {
        lld koszt=v[i].f;
        int a=v[i].s.f;
        int b=v[i].s.s;
        if(zlacz(a,b))wyn+=koszt;
    }
    printf("%lld\n",wyn);
}