复习版
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define not !
#define and &&
#define or ||
#define ri register int
#define rep(inc, frm, to) for (ri inc = frm; inc < (to); ++inc)
#define rep2(inc, frm, to) for (ri inc = frm; inc > (to); --inc)
#define setbit(x, y) x |= 1 << y
#define clrbit(x, y) x &= ~(1 << y)
#define getbit(x, y) x >> y & 1
#define flipbit(x, y) x ^= 1 << y
#define show_bin(x) { rep2(i, 31, ~0) printf("%d%c", getbit(x, i), i ? 9 : 10); }
#define SWAP(a, b) { typeof(a) tmp = a; a = b; b = tmp; }
typedef long long int ll;
#define r() fast_read()
bool is_digit(const char c) {
return c >= 48 and c <= 57;
}
ll my_pow(int base, int exponent) {
return exponent ? my_pow(base, exponent - 1) * base : 1;
}
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
ll fast_read(void) {
ll n = 0, sign = 1;
char c = getchar();
while (not is_digit(c)) {
if (c == '-') sign = ~0;
c = getchar();
}
while (is_digit(c)) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}
typedef struct {
int* parents;
int count;
} UF;
void InitUF(UF* uf, int count, const size_t len) {
uf->parents = malloc(len * sizeof(int));
for (int i = 0; i < len; ++i) uf->parents[i] = i;
uf->count = count;
}
int Find(UF* uf, int x) {
if (uf->parents[x] ^ x)
uf->parents[x] = Find(uf, uf->parents[x]);
return uf->parents[x];
}
int Unite(UF* uf, int u, int v) {
u = Find(uf, u), v = Find(uf, v);
if (u == v) return 0;
uf->parents[u] = v;
--uf->count;
return 1;
}
int IsConnected(UF* uf, int u, int v) {
return Find(uf, u) == Find(uf, v);
}
void DestroyUF(UF* uf) {
free(uf->parents);
}
#define MAX_N 110
int edge_cnt;
typedef struct Edge Edge;
struct Edge {
int u, v, w;
} edges[MAX_N * MAX_N];
int cmp(const void* a, const void* b) {
return ((Edge*) a)->w - ((Edge*) b)->w;
}
int n;
void kruskal(const int n) {
UF uf;
InitUF(&uf, n, MAX_N);
int ans = 0, cnt = 0, u, v, w;
rep(e, 0, edge_cnt) {
u = edges[e].u, v = edges[e].v, w = edges[e].w;
if (not Unite(&uf, u, v)) continue;
ans += w;
if (++cnt == n - 1) break;
}
printf("%d\n", ans);
DestroyUF(&uf);
}
signed main(int argc, char const *argv[]) {
// freopen("test.in", "r", stdin);
while ((n = r())) {
edge_cnt = 0; // init
int u, v, w;
rep(i, 0, n * (n - 1) >> 1) {
u = r(), v = r(), w = r();
edges[edge_cnt++] = (Edge) {u, v, w};
}
qsort(edges, edge_cnt, sizeof(Edge), cmp);
kruskal(n);
}
// fclose(stdin);
return ~~(0 ^ 0);
}
Kruskal
#include <iostream>
#include <algorithm>
#define f(inc, frm, to) for (size_t inc = frm; inc < to; ++inc)
using namespace std;
const int N = 1E2 + 1E1;
int edge_cnt;
struct Edge {
int u, v, w;
bool operator<(const Edge& o) const {
return w < o.w;
}
} edges[N * N];
struct UF {
public:
UF() { f(i, 0, N) p_[i] = i; }
int find(int x) {
if (p_[x] ^ x) p_[x] = find(p_[x]);
return p_[x];
}
bool unite(int p, int q) {
int root_p = find(p), root_q = find(q);
if (root_p == root_q) return false;
p_[root_p] = root_q;
return true;
}
private:
int p_[N];
};
int n;
inline int kruksal(void) {
sort(edges, edges + edge_cnt);
UF uf;
int tot_cost = 0, cnt = 0;
f(e, 0, edge_cnt) {
int u = edges[e].u, v = edges[e].v, w = edges[e].w;
if (not uf.unite(u, v)) continue;
tot_cost += w;
if (++cnt == n - 1) return tot_cost;
}
return 0;
}
int main(int argc, char const *argv[]) {
while (scanf("%d", &n), n) {
edge_cnt = 0;
int u, v, w;
f(i, 0, n * (n - 1) / 2) {
scanf("%d%d%d", &u, &v, &w);
edges[edge_cnt++] = {u, v, w};
}
printf("%d\n", kruksal());
}
return 0;
}