1751.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1751 on 2005-10-03 at 21:26:29 */ 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define  MAX  500
#define  MAX_ROAD  1000

class BSTreeNode {
public:
	char name[32];
	int order;
	BSTreeNode *left;
	BSTreeNode *right;
	void init(char *s, int o) {
		left = NULL;
		right = NULL;
		order = o;
		strcpy(name, s);
	}
	void add(BSTreeNode *node) {
		BSTreeNode *p = this;
		int i;
        while(true) {
            i = strcmp(node->name, p->name);
            if(i < 0) {
                if(p->left != NULL) {
                    p = p->left;
                } else {
                    p->left = node;
                    return;
                }
            } else if(i > 0) {
                if(p->right != NULL) {
                    p = p->right;
                } else {
                    p->right = node;
					return;
                }
            } else {
                return;
            }
        }
	}
	int search(char *key) {
        BSTreeNode *p = this;
        while(true) {
            int i = strcmp(key, p->name);
            if(i < 0) {
                if(p->left != NULL) {
                    p = p->left;
                } else {
                    return 0;
                }    
            } else if(i > 0) {
                if(p->right != NULL) {
                    p = p->right;
                } else {
                    return 0;
                }
            } else {
                return p->order;
            }    
        }
    }
};

class UFSet {
public:
	int father[MAX+1];
	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 {
	double d;
	int cityA;
	int cityB;
} Road;

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

int main()
{
	UFSet *uf = new UFSet;
	BSTreeNode *Node[MAX+1], *root;
	Road road[MAX_ROAD+1];
	bool runshort;
	int i, fa, fb;
	int nodeN, roadN;
	double cabLen, total;
	char name[32], namex[32];
	
	for(i = 0; i < MAX; i++) {
		Node[i] = new BSTreeNode;
	}
	while(scanf("%lf", &cabLen) == 1) {
		root = NULL;
		scanf("%d", &nodeN);
		for(i = 0; i < nodeN; i++) {
			scanf("%s", name);
			Node[i]->init(name, i);
			if(root == NULL) {
				root = Node[i];
			} else {
				root->add(Node[i]);
			}
		}
		scanf("%d", &roadN);
		for(i = 0; i < roadN; i++) {
			scanf("%s %s %lf", name, namex, &road[i].d);
			road[i].cityA = root->search(name);
			road[i].cityB = root->search(namex);
		}
		qsort(road, roadN, sizeof(Road), cmp);
		total = 0;
		uf->makeSet();
		runshort = false;
		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);
				if(total - cabLen > 1e-2) {
					runshort = true;
					break;
				}
			}
		}
		if(runshort) {
			printf("Not enough cable\n");
		} else {
			printf("Need %.1lf miles of cable\n", total);
		}
	}
	
	return 0;
}

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