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 <algorithm>
using namespace std;

#define st first
#define nd second
#define make(b,c) make_pair(b,c);
const int N=2005, inf=1<<30;

int fu[N], ile, n;
int G[N][N];

int fuf(int a)
{
	if (fu[a]==a) return a;
	fu[a] = fuf( fu[a] );
	return fu[a];
}

inline void fuu(int a,int b)
{
	ile--;
	fuf(a);
	fuf(b);
	for (int i=1;i<=n+1;i++) G[i][ fu[b] ] = G[ fu[b] ][i] = min( G[ fu[a] ][i], G[ fu[b] ][i] );
	fu[ fu[a] ] = fu[b];
}

int main()
{
	int a, k;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		for (int j=i+1;j<=n+1;j++)
		{
			scanf("%d",&a);
			G[i][j] = G[j][i] = a;
		}
	for (int i=1;i<=n+1;i++) G[i][0] = inf;
	for (int i=1;i<=n+1;i++) fu[i] = i;	
	ile = n+1;
	long long int wynik=0;
	while ( ile > 1 )
	{
//		printf("lev\n");
		for (int x=1;x<=n+1;x++)
			if (fu[x]==x)
			{
				k = 0; 
				for (int i=1;i<=n+1;i++)
					if ( fuf(i)!=x && G[x][i] < G[x][ k ]) k = i;
				wynik += G[ x ][ k ];
				fuu( k , x );
			}
	}
	printf("%lld\n",wynik);
}