2790306_ac_950ms_4044k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#define MAX 1001
#define INF 2100000000

int n, q;
int W, ans;
int cost[MAX][MAX];
int num[] = {1,2,4,8,16,32,64,128,256,512};

struct node
{
	int no;
	int cost;
	int pos[1001];
}sub[9];

struct Node
{
	int x, y;
}pot[MAX];

void prim()
{
	int i, j, k;
	int min;
	int lowcost[MAX];

	for(i = 0; i < n; i++)
		lowcost[i] = cost[0][i];
	for(i = 1; i < n; i++)
	{
		min = INF;
		for(j = 0; j < n; j++)
			if(lowcost[j]!=-1&&lowcost[j]<min)
			{
				min = lowcost[j];
				k = j;
			}
			W += min;
			lowcost[k] = -1;
		for(j = 0; j < n; j++)
			if(cost[k][j]!=-1&&cost[k][j]<lowcost[j])
				lowcost[j] = cost[k][j];
	}
}

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

void init()
{
	int i, j;

	for (i = 0; i < q; i++)
	{
		scanf("%d%d",&sub[i].no,&sub[i].cost);
		for(j = 0; j < sub[i].no; j++)
		{
			scanf("%d",&sub[i].pos[j]);
			sub[i].pos[j]--;
		}
	}
	for (i = 0; i < n; i++)
		scanf("%d%d",&pot[i].x,&pot[i].y);
	for (i = 0; i < n; i++)
	{
		cost[i][i] = -1;
		for (j = i+1; j < n; j++)
			cost[i][j] = cost[j][i] = dis(i,j);
	}
}

void modify(int s,int t)
{
	int i, j, k;

	W = 0;
	for(i = 0; i < q; i++)
	{
		if(s&num[i])
		{
			W += sub[i].cost;
			for(j = 0; j < sub[i].no; j++)
				for(k = j+1; k < sub[i].no; k++)
					cost[sub[i].pos[j]][sub[i].pos[k]] = cost[sub[i].pos[k]][sub[i].pos[j]] = (t?dis(sub[i].pos[j],sub[i].pos[k]):0);
		}
	}
	
}

int main()
{
	int i, no;

	scanf("%d%d",&n,&q);
	init();
	ans = INF;
	no = 1<<q;
	for (i = 0; i < no; i++)
	{
		modify(i,0);
		prim();
		if(W<ans)
			ans = W;
		modify(i,1);	
	}
	printf("%d\n",ans);
	return 1;
}