1632.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1632 on 2005-10-04 at 18:48:03 */ 
#include <cstdio>
#include <cstdlib>
#define  MAX  32
#define  ROAD_MAX  128

class UFSet {
public:
	int father[MAX];
	void makeSet() {
		int i;
		for(i = 0; i < MAX; i++) {
			father[i] = -1;
		}
	}
	int findFather(int x) {
		if(father[x] == -1) {
			return x;
		} else {
			return findFather(father[x]);
		}
	}
	void unionSet(int x, int y) {
		int fatherX = findFather(x);
		int fatherY = findFather(y);
		if(fatherX != fatherY) {
			father[fatherX] = fatherY;
		}
	}
};

typedef struct {
	long d;
	int cityA;
	int cityB;
} Road;

int cmp(const void*, const void*);

int main()
{
	UFSet *uf = new UFSet;
	Road road[ROAD_MAX];
	int n, roadN;
	int i, j, fa, fb, dcN;
	char scity[4], dcity[4];
	long total;
	
	while(scanf("%d", &n) == 1) {
		if(n == 0) {
			return 0;
		} else {
			roadN = 0;
			for(i = 0; i < n - 1; i++) {
				scanf("%s %d", scity, &dcN);
				for(j = 0; j < dcN; j++) {
					getchar();
					scanf("%c %ld", dcity, &road[roadN].d);
					road[roadN].cityA = scity[0] - 'A';
					road[roadN].cityB = dcity[0] - 'A';
					roadN++;
				}
			}
			qsort(road, roadN, sizeof(Road), cmp);
			total = 0;
			uf->makeSet();
			for(i = 0; i < roadN; i++) {
				fa = uf->findFather(road[i].cityA);
				fb = uf->findFather(road[i].cityB);
				if(fa != fb) {
					total += road[i].d;
					uf->unionSet(road[i].cityA, road[i].cityB);
				}
			}
			printf("%ld\n", total);
		}
	}
	
	return 0;
}

int cmp(const void *a, const void *b)
{
	Road *x = (Road*)a, *y = (Road*)b;
	
	if(x->d < y->d) {
		return -1;
	} else {
		return 1;
	}
}