1658.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1658 on 2006-06-25 at 14:09:57 */ 
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;

const int L = 32, PN = 32;
const int RN = 256;
const int INF = 1 << 20;

class UFSet {
public:
	int parent[PN];
	void make() { memset(parent, -1, sizeof(parent)); }
	int find(int);
	void unionSet(int, int);
};
int UFSet::find(int x) {
	if(parent[x] == -1) return x;
	else {
		parent[x] = find(parent[x]);
		return parent[x];
	}
}
void UFSet::unionSet(int x, int y) {
	int pX = find(x), pY = find(y);
	if(pX != pY) parent[pX] = pY;
}

class Road {
public:
	int a, b, d;
	bool used;
	void set(int o1, int o2, int cd) { a = o1; b = o2; d = cd; used = false; }
	bool operator <(const Road& r) const { return d < r.d; }
};

struct cmp {
	bool operator ()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};

map<const char*, int, cmp> dict;
int hn, parkO;

int findIndex(const char*);

int main()
{
	UFSet uf;
	Road road[RN];
	char name[PN][L];
	int t, T, i, j;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		int o[2], n;
		scanf("%d", &n);
		parkO = -1; hn = 0; dict.clear();
		for(i = 0; i < n; i++) {
			for(j = 0; j < 2; j++) {
				scanf("%s", name[hn]);
				o[j] = findIndex(name[hn]);
			}
			int d; scanf("%d", &d);
			if(o[1] == parkO) swap(o[0], o[1]);
			road[i].set(o[0], o[1], d);
		}
		int total = 0, parked = 0, parkLmt;
		scanf("%d", &parkLmt);
		sort(road, road+n);
		uf.make();
		for(i = 0; i < n; i++) {
			int fa = uf.find(road[i].a), fb = uf.find(road[i].b);
			if(fa != fb) {
				total += road[i].d; road[i].used = true;
				uf.unionSet(road[i].a, road[i].b);
				if(road[i].a == parkO) parked++;
			}
		}
		for(; parked > parkLmt; parked--) {
			int minD = INF, ir = -1, er = -1;
			for(i = 0; i < parked; i++) {
				uf.make();
				int vp = 0, dr;
				for(j = 0; j < n; j++)
					if(!road[j].used) continue;
					else if(road[j].a == parkO && vp++ == i) dr = j;
					else uf.unionSet(road[j].a, road[j].b);
				for(j = 0; j < n; j++)
					if(road[j].used || uf.find(road[j].a) == uf.find(road[j].b)) continue;
					else if(road[j].a == parkO) continue;
					else if(minD > road[j].d-road[dr].d) { ir = j; er = dr; minD = road[j].d-road[dr].d; }
			}
			total += minD; road[er].used = false; road[ir].used = true;
		}
		if(t != 0) putchar('\n');
		printf("Total miles driven: %d\n", total);
	}

	return 0;
}

int findIndex(const char* str)
{
	if(!dict.count(str)) dict[str] = hn++;
	int r = dict.find(str)->second;
	if(!strcmp(str, "Park")) parkO = r;
	return r;
}