2064.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2064 on 2006-01-07 at 18:01:32 */ 
#include <cstdio>
#include <cstring>
#include <cmath>

const int MAX = 1024;
const int LIMIT = 30;

class UFSet {
public:
	int parent[MAX];
	void make();
	int find(int);
	void unionSet(int, int);
};
void UFSet::make() {
	memset(parent, -1, sizeof(parent));
}
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 Village {
public:
	int x, y, n;
	void make();
	bool visit(const Village&) const;
};
void Village::make() {
	scanf("%d %d %d", &x, &y, &n);
}
bool Village::visit(const Village& v) const {
	return (x-v.x)*(x-v.x)+(y-v.y)*(y-v.y) <= LIMIT*LIMIT;
}

int main()
{
	UFSet ufs;
	Village v[MAX];
	int i, j;
	int monk[MAX], n;
	
	while(scanf("%d", &n) != EOF && n != 0) {
		ufs.make();
		for(i = 0; i < n; i++) {
			v[i].make();
			for(j = 0; j < i; j++) {
				if(v[i].visit(v[j])) ufs.unionSet(i, j);
			}
		}
		memset(monk, 0, sizeof(monk));
		for(i = 0; i < n; i++) monk[ufs.find(i)] += v[i].n;
		int max = -1, mn;
		for(i = 0; i < n; i++) {
			if(monk[ufs.find(i)] > max) max = monk[ufs.find(i)], mn = i+1;
		}
		printf("%d %d\n", mn, max);
	}
	
	return 0;
}