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
88
89
90
91
92
93
94
95
96
97
#include<cstdio>
#include<tuple>
#include<algorithm>
#define MAXK 2005
using namespace std;

class FindAndUnion{
	private:
		int *rank, *parent;
		int _size;
	public:
		FindAndUnion(int size);
		~FindAndUnion();
		int find(int v);
		void join(int u, int v);
		bool the_same(int u, int v);
		int size();
};

FindAndUnion::FindAndUnion(int size):_size(size){
	this->rank = new int[size];
	this->parent = new int[size];
	for(int i=0;i<size;i++){
		this->rank[i] = 0;
		this->parent[i] = i;
	}
}

FindAndUnion::~FindAndUnion(){
	delete[] this->rank;
	delete[] this->parent;
}

int FindAndUnion::find(int u){
	int v = u;
	while(this->parent[v] != v)
		v = this->parent[v];

	while(this->parent[u] != u){
		int t = this->parent[u];
		this->parent[u] = v;
		u = t;
	}
	return v;
}

void FindAndUnion::join(int u, int v){
	u = this->find(u);
	v = this->find(v);

	if(this->rank[u] > this->rank[v])
		this->parent[v] = u;
	else{
		this->parent[u] = v;
		if(this->rank[u] == this->rank[v])
			this->rank[v]++;
	}
}

bool FindAndUnion::the_same(int u, int v){
	return this->find(u) == this->find(v);
}

int FindAndUnion::size(){
	return this->_size;
}

int n;


int main(){
	scanf("%d",&n);
	vector<tuple<int,int,int> > V;

	for(int i=0;i<n;i++){
		for(int j=i;j<n;j++){
			int v;
			scanf("%d",&v);
			V.push_back(make_tuple(v,i,j));

		}
	}
	sort(V.begin(),V.end());

	long long ile = 0;
	FindAndUnion FU(n+1);

	for(int i=0;i<V.size();i++){
		int a = std::get<1>(V[i]), b = std::get<2>(V[i]);
		if(FU.the_same(a,b+1))
			continue;
		ile+=get<0>(V[i]);
		FU.join(a,b+1);
	}

	printf("%lld\n",ile);
}