#include<stdio.h>
#define MAX 10
//#define MAX 5000001
typedef struct {
int u, v, w;
} EDGE;
EDGE G[MAX];
int P[MAX]; /* Parent */
int R[MAX]; /* Rank */
#define Swap(a, b) { EDGE t = a; a = b; b = t; }
void QSort(int l, int r) {
int i = l, j = r;
int p = G[(l + r) / 2].w;
while (i <= j) {
while (G[i].w < p) ++i;
while (G[j].w > p) --j;
if (i <= j) { Swap(G[i], G[j]); ++i; --j; }
}
if (l < j) QSort(l, j);
if (i < r) QSort(i, r);
}
int FindSet(int u) {
if (u == P[u]) return u;
return P[u] = FindSet(P[u]);
}
void UnionSet(int u, int v) {
u = FindSet(u);
v = FindSet(v);
if (u == v) return;
if (R[u] > R[v]) { int t = u; u = v; v = t; }
P[u] = v;
if (R[u] == R[v]) ++R[u];
}
int main() {
freopen("input.txt", "r", stdin);
int T, t, N, M, i, ec, mc;
scanf("%d", &T);
for (t = 1; t <= T; ++t) {
scanf("%d %d", &N, &M);
for (i = ec = 0; i < M; ++i, ++ec)
scanf("%d %d %d", &G[i].u, &G[i].v, &G[i].w), P[i] = i, R[i] = 0;
QSort(0, ec - 1);
for (mc = i = 0; i < ec; ++i) {
if (FindSet(G[i].u) == FindSet(G[i].v)) continue;
mc += G[i].w;
UnionSet(G[i].u, G[i].v);
}
printf("#%d %d\n", t, mc);
}
return 0;
}
댓글