3118219_ac_979ms_3524k.c

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

# include <stdio.h>
# include <stdlib.h>
# define MAXV 751
# define MAXE 300000

typedef struct enode
{
	int v1;
	int v2;
	int weight;
}Edge;

Edge E[MAXE];
int vest[MAXV];

int cmp(const void *a, const void *b)
{
	struct enode *aa = (struct enode *)a;
	struct enode *bb = (struct enode *)b;
	return aa->weight-bb->weight;
}

void kruskal(Edge E[], int n)
{
	int i, j, k;
	int m1, m2, sn1, sn2;
	
	j = 0;
	k = 1;
	while(k < n)
	{
		m1 = E[j].v1; m2 = E[j].v2;
		sn1 = vest[m1]; sn2 = vest[m2];
		if(sn1!=sn2)
		{
			k++;
			if(E[j].weight!=0)
			{
				printf("%d %d\n",E[j].v1+1,E[j].v2+1);
			}
			for(i = 0; i < n; i++)
			{
				if(vest[i]==sn2)
				{
					vest[i] = sn1;
				}
			}
		}
		j++;
	}
}

int main()
{
	int N, Q, tmp;
	int i, j, k;
	int a, b;
	int pt[MAXV][2];

	scanf("%d",&N);
	k = 0;
	for(i = 0; i < N; i++)
		scanf("%d%d",&pt[i][0],&pt[i][1]);
	for(i = 0; i < N; i++)
		for(j = i+1; j < N; j++)
		{
			tmp = (pt[i][0]-pt[j][0])*(pt[i][0]-pt[j][0])+(pt[i][1]-pt[j][1])*(pt[i][1]-pt[j][1]);
			E[k].v1 = i;
			E[k].v2 = j;
			E[k].weight = tmp;
			k++;
		}
	for(i = 0; i < N; i++)
		vest[i] = i;
	scanf("%d",&Q);
	for(i = 0; i < Q; i++)
	{
		scanf("%d%d",&a,&b);
		a--;b--;
		if(a > b)
		{
			tmp = a;
			a = b;
			b = tmp;
		}
		E[b-a-1+a*(2*N-a-1)/2].weight = 0;
	}
	qsort(E,N*(N-1)/2,sizeof(E[0]),cmp);
	kruskal(E,N);
	return 1;
}