3250145_ac_297ms_4048k.cpp

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

# include <stdio.h>
# define MAX 2001
# define INF 2100000000

int W;
char cost[MAX][MAX];
char name[MAX][8];

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

	W = 0;
	for(i = 0; i < n; i++)
		lowcost[i] = cost[v][i];
	for(i = 1; i < n; i++)
	{
		min = INF;
		for(j = 0; j < n; j++)
			if(lowcost[j]!=0&&lowcost[j]<min)
			{
				min = lowcost[j];
				k = j;
			}
			W += min;
			lowcost[k] = 0;
		for(j = 0; j < n; j++)
			if(cost[k][j]!=0&&cost[k][j]<lowcost[j])
				lowcost[j] = cost[k][j];
	}
	printf("The highest possible quality is 1/%d.\n",W);
}

int dis(int i,int j)
{
	int k, tmp =0;

	for(k = 0; k < 7; k++)
		tmp += (name[i][k]!=name[j][k]);
	return tmp;
}

void init(int n)
{
	int i, j;

	for(i = 0; i < n; i++)
		scanf("%s",name[i]);
	for(i = 0; i < n; i++)
	{
		cost[i][i] = 0;
		for(j = i+1; j < n; j++)
			cost[i][j] = cost[j][i] = dis(i,j);
	}
}
int main()
{
	int n;

	while(scanf("%d",&n)==1,n)
	{
		init(n);
		prim(n,0);
	}
	return 1;
}