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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

struct node{
	int key;
	int size;
	node *father;
};

node * find(node * x){
	node * n = x;
	while(n->father != n) n = n->father;
	return n;
}

void uni(node * x, node * y){
	if(x==NULL || y==NULL) return;
	if(x->size > y->size){
		x->size += y->size;
		y->father = x;
		y = NULL;
		delete y;
	}
	else{
		y->size += x->size;
		x->father = y;
		x = NULL;
		delete x;
	}
}

int main(){
	int n, c, res=0;
	scanf("%d", &n);
	vector<pair<int, pair<int,int> > > edges;
	node *ind[n+10];
	node *t[n+10];
	for(int i=0; i<n+1; i++){
		node *x = new node;
		x->key=i;
		x->father = x;
		x->size = 1;
		ind[i] = x;
		t[i] = x;
	}
	
	for(int i=1; i<=n; i++){
		for(int j=i; j<=n+1-i; j++){
			scanf("%d", &c);
			edges.push_back(make_pair (c, (make_pair (i-1, j+i-1))));
		}
	}
	sort(edges.rbegin(), edges.rend());
	
	int help=n-1, f, s;
	node * g;
	node * h;
	pair<int, pair<int,int> > m;
	while(help>0){
		m = edges.back();
		edges.pop_back();
		f = m.second.first; s = m.second.second;
		g=find(ind[f]);
		h=find(ind[s]);
		if(g != h){
			res += m.first;
			uni(g, h);
			help--;
		}
	}
	printf("%d\n", res);

// 	printf("%d\n", find(ind[0])->key);
// 	uni(t[1],t[2]);
// 	printf("%d\n", find(ind[1])->key);
// 	printf("%d\n", find(ind[2])->key);
// 	printf("%d\n", (t[1]==NULL));
// 	printf("%d\n", (t[2]==NULL));
// 	printf("%d\n", (ind[1]==NULL));
// 	printf("%d\n", (ind[2]==NULL));
	
	
	return 0;
}