pku2784.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define size 1001
#define TheMax 1000000000
using namespace std;

typedef struct Edge
{
	int s, e, d;
}Edge;

typedef struct Point
{
	int x, y;
}Point;

typedef struct Net
{
	int N, cost;
	int pos[1000];
}Net;

Edge E[size * size / 2];
Point p[size];
Net Nt[8];
int father[size];
int N, Q, E_k, ans;

int Calc_Dis(int i, int j)
{
	return (p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y);
}

bool cmp(const Edge &a, const Edge &b)
{
	return a.d < b.d;
}

void CreateEdge()
{
	int i, j, k;
	for (i = 1, k = 0; i <= N; i++)
	{
		for (j = i + 1; j <= N; j++)
		{
			E[k].s = i;
			E[k].e = j;
			E[k].d = Calc_Dis(i, j);
			k++;
		}
	}
	E_k = k;
	sort(E, E + E_k, cmp);
}

int Get_ID(int x)
{
	int root;
	if (father[x] == 0)
	{
		return x;
	}
	root = Get_ID(father[x]);
	father[x] = root;
	return root;
}

int Kruscal(int x)
{
	int cnt, v, cost;
	int i, j;
	int hs, he;
	memset(father, 0, sizeof(father));
	cnt = 0;
	cost = 0;
	for (i = 0; i < Q; i++)
	{
		if (x & (1 << i))
		{
			cost += Nt[i].cost;
			for (j = 1; j < Nt[i].N; j++)
			{
				hs = Get_ID(Nt[i].pos[0]);
				he = Get_ID(Nt[i].pos[j]);
				if (hs != he)
				{
					father[he] = hs;
					cnt++;
				}
			}
		}
	}
	for (i = 0, j = 1; j < N - cnt; i++)
	{
		hs = Get_ID(E[i].s);
		he = Get_ID(E[i].e);
		if (hs == he)
		{
			continue;
		}
		father[he] = hs;
		cost += E[i].d;
		j++;
	}
	return cost;
}

int main()
{
	int i, j, tmp;
	while (EOF != scanf("%d %d", &N, &Q))
	{
		for (i = 0; i < Q; i++)
		{
			scanf("%d %d", &Nt[i].N, &Nt[i].cost);
			for (j = 0; j < Nt[i].N; j++)
			{
				scanf("%d", &Nt[i].pos[j]);
			}
		}
		for (i = 1; i <= N; i++)
		{
			scanf("%d %d", &p[i].x, &p[i].y);
		}
		CreateEdge();
		ans = TheMax;
		for (i = 0; i < (1 << Q); i++)
		{
			tmp = Kruscal(i);
			if (tmp < ans)
			{
				ans = tmp;
			}
		}
		printf("%d\n", ans);
	}	
	return 0;
}