2162.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2162 on 2006-03-08 at 22:50:31 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 1024;
const int INF = 1 << 30;

class UFSet {
private:
	int parent[MAX];
public:
	UFSet() { 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 SubNet {
public:
	int cost, n, city[MAX];
	void make();
};
void SubNet::make() {
	int i; scanf("%d %d", &n, &cost);
	for(i = 0; i < n; i++) { scanf("%d", &city[i]); city[i]--; }
}

class Town {
public:
	int x, y;
	void make() { scanf("%d %d", &x, &y); }
	int cost(const Town& t) const { return (x-t.x)*(x-t.x)+(y-t.y)*(y-t.y); }
};

int n, c, best;
SubNet net[8];
Town town[MAX];

void build(int);

int main()
{
	int i;
	
	while(scanf("%d %d", &n, &c) != EOF) {
		for(i = 0; i < c; i++) net[i].make();
		for(i = 0; i < n; i++) town[i].make();
		best = INF; int status = 1 << c;
		for(i = 0; i < status; i++) 
			build(i);
		printf("%d\n", best);
	}
	
	return 0;
}

void build(int status)
{
	int i, j, cost = 0;
	for(i = 0; i < c; i++)
		if(status & (1 << i)) cost += net[i].cost;
	if(cost >= best) return;
	UFSet ufs;
	for(i = 0; i < c; i++)
		if(status & (1 << i))
			for(j = 1; j < net[i].n; j++)
				ufs.unionSet(net[i].city[0], net[i].city[j]);
	int d[MAX], prev = -1;
	bool vst[MAX] = { false };
	for(i = 0; i < n; i++) d[i] = INF;
	d[ufs.find(0)] = 0;
	for(i = 0; i < n && cost < best; i++) {
		int mind = INF, mini;
		for(j = 0; j < n; j++)
			if(!vst[j] && d[ufs.find(j)] < mind) 
				{ mind = d[ufs.find(j)]; mini = j; }
		if(mind == INF) break;
		vst[mini] = true;
		for(j = 0; j < n; j++)
			d[ufs.find(j)] = min(d[ufs.find(j)], town[mini].cost(town[j]));
		if(prev != -1 && ufs.find(prev) != ufs.find(mini)) cost += mind;
		prev = mini;
	}
	best = min(cost, best);
}