You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
42 lines
998 B
C++
42 lines
998 B
C++
#include <cstdio>
|
|
#include <algorithm>
|
|
#include <queue>
|
|
using namespace std;
|
|
struct edge
|
|
{
|
|
int f, t, l;
|
|
};
|
|
bool operator<(const edge &lhs, const edge &rhs)
|
|
{
|
|
return lhs.l > rhs.l;
|
|
}
|
|
int fa[111], n;
|
|
int f(int x) { return x == fa[x] ? x : fa[x] = f(fa[x]); }
|
|
int main()
|
|
{
|
|
while (scanf("%d", &n), n)
|
|
{
|
|
int ans = 0;
|
|
priority_queue<edge> q;
|
|
for (int i = n * (n - 1) / 2, x, y, z; i; i--)
|
|
scanf("%d%d%d", &x, &y, &z), q.push({x, y, z});
|
|
for (int i = 1; i <= n; i++)
|
|
fa[i] = i;
|
|
int cnt = n;
|
|
while (!q.empty())
|
|
{
|
|
edge e = q.top();
|
|
q.pop();
|
|
if (f(e.f) != f(e.t))
|
|
{
|
|
//printf("---%d %d %d\n", e.f, e.t, e.l);
|
|
fa[f(e.f)] = f(e.t);
|
|
ans += e.l;
|
|
cnt--;
|
|
if (cnt == 1) break;
|
|
}
|
|
}
|
|
printf("%d\n", ans);
|
|
}
|
|
return 0;
|
|
} |