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 <iostream>
#include <istream>
#include <ostream>
#include <vector>
#include <algorithm>
using namespace std;
struct UnionFindSet {
std::vector<int> root;
std::vector<int> height;
UnionFindSet(int size = 10) {
root = std::vector<int>(size);
for (int i = 0; i < size; i++) root[i] = i;
height = std::vector<int>(size, 0);
}
int find(int node) {
if (root[node] != node) {
root[node] = find(root[node]);
}
return root[node];
}
void join(int node1, int node2) {
int root1 = find(node1), root2 = find(node2);
if (root1 == root2) return;
if (height[root1] > height[root2]) {
root[root2] = root1;
} else if (height[root2] > height[root1]) {
root[root1] = root2;
} else {
root[root2] = root1;
height[root1]++;
}
}
};
struct Edge {
int from;
int to;
int weight;
Edge() = default;
Edge(int from, int to, int weight) {
this->from = from;
this->to = to;
this->weight = weight;
}
Edge reverse() {
return Edge(to, from, weight);
}
friend bool operator<(const Edge& a, const Edge& b) {
return a.weight < b.weight;
}
friend std::ostream& operator<<(std::ostream& out, const Edge& edge) {
out << edge.from << "->" << edge.to;
return out;
}
friend std::istream& operator>>(std::istream& in, Edge& edge) {
in >> edge.from >> edge.to >> edge.weight;
return in;
}
};
int main() {
int villageSize = 0;
while (std::cin >> villageSize) {
if (!villageSize) break;
int size = (villageSize-1)*villageSize/2;
std::vector<Edge> edges(size);
for (int i = 0; i < size; i++) {
std::cin >> edges[i];
}
std::sort(edges.begin(), edges.end());
UnionFindSet set(villageSize+1);
int reachSize = 0, totalCost = 0;
for (int i = 0; i < size; i++) {
Edge& edge = edges[i];
if (set.find(edge.from) == set.find(edge.to)) {
continue;
}
set.join(edge.from, edge.to);
totalCost += edge.weight;
reachSize++;
if (reachSize >= villageSize) break;
}
std::cout << totalCost << std::endl;
}
return 0;
}
|
