2196136_ac_15ms_384k.c

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

# include <stdio.h>
# include <math.h>
# include <stdlib.h>

int n, m, t = 1;
struct node
{
	int st;
	int ed;
	double w;
}E[200*200];

int cmp(const void *a,const void *b)
{
	struct node *aa = (struct node *)a;
	struct node *bb = (struct node *)b;
	return aa->w-bb->w>0?1:-1;
}

void kruskal()
{
	int i, j, k;
	int vest[1001];
	int sn1, sn2;
	double max;
	
	for(i = 0; i < n; i++)
		vest[i] = i;
	j = 0;k = 1;max = -1;
	while(k < n)
	{
		if(vest[0]==vest[1])
			break;
		sn1 = vest[E[j].st]; sn2 = vest[E[j].ed];
	    if(sn1!=sn2)
		{
			k++;
			if(E[j].w-max>0)
				max = E[j].w;
	   	    for(i = 0; i < n; i++)
				if(vest[i]==sn2)
					vest[i] = sn1;
		}
		j++;
	}
	printf("Scenario #%d\n",t++);
	printf("Frog Distance = %.3lf\n\n",max);
}

int input()
{
	int i, j;
	int x[201], y[201];

	scanf("%d",&n);
	if(!n)
		return 0;
	m = 0;
	for(i = 0; i < n; i++)
		scanf("%d%d",&x[i],&y[i]);
	for(i = 0; i < n-1; i++)
		for(j = i+1; j < n; j++)
		{
			E[m].st = i;E[m].ed = j;
			E[m++].w = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		}
	qsort(E,m,sizeof(E[0]),cmp);
	kruskal();
	return 1;
}

int main()
{
	while(input());
	return 1;
}