枫原万叶 • 1个月前
using namespace std;
int fa[N], Size[N], n;
struct node {
int u, v, w;
} e[N];
bool cmp(node &a, node &b) {
return a.w < b.w;
}
void init() {
for (int i = 0; i <= n; i++) {
fa[i] = i;
Size[i] = 1;
}
}
int find(int i) {
if (i == fa[i])
return i;
else {
fa[i] = find(fa[i]);
return fa[i];
}
}
void unionn(int i, int j) {
int ifa = find(i);
int jfa = find(j);
fa[jfa] = ifa;
}
void kruskal() {
sort(e, e + n - 1, cmp);
int res = 0;
for (int i = 0; i < n - 1; i++) {
int a = find(e[i].u), b = find(e[i].v), w = e[i].w;
if (a != b) {
res += (Size[a] * Size[b] - 1) * (w + 1);
fa[a] = b;
Size[b] += Size[a];
}
}
cout << res << endl;
}
int main() {
cin >> n;
for (int i = 0; i < n - 1; i++) {
cin >> e[i].u >> e[i].v >> e[i].w;
}
init();
kruskal();
return 0;
}
评论:
请先登录,才能进行评论