POJ

//见《挑战程序设计竞赛》第2.5.6节 #include<cstdio> #include<algorithm> using namespace std; #define MAX_N 20000 #define MAX_E 50000 int par[MAX_N]; int ran[MAX_N]; void init(int n) { for (int i = 0; i < n; i++) { par[i] = i; ran[i] = 0; } } int find(int x) { if (par[x] == x) return x; else return par[x] = find(par[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (ran[x] < ran[y]) par[x] = y; else { par[y] = x; if (ran[x] == ran[y]) ran[x]++; } } bool same(int x, int y) { return find(x) == find(y); } struct edge { int u, v, cost; }es[MAX_E]; bool compare(const edge& e1, const edge& e2) { return e1.cost > e2.cost; }; int main() { int T, N, M, R, save, all; scanf("%d", &T); while (T--) { scanf("%d%d%d", &N, &M, &R); all = N + M; for (int i = 0; i < R; i++) { scanf("%d%d%d", &es[i].u, &es[i].v, &es[i].cost); es[i].v += N; } sort(es, es + R, compare); init(all); save = 0; for (int i = 0; i < R; i++) { if (!same(es[i].u, es[i].v)) { unite(es[i].u, es[i].v); save += es[i].cost; } } printf("%d\n", (N + M) * 10000 - save); } }