2148929_ac_0ms_108k.c

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

//Kruskal again
# include <stdio.h>
# include <stdlib.h>

int n, m;
struct node
{
	int st;
	int ed;
	int w;
}E[5000];

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;
}

void kruskal()
{
	int MSW = 0;
	int i, j, k, W, J;
	int vest[101], tmpvest[101];
	int sn1, sn2;
	
	for(i = 0; i < n; i++)
		vest[i] = tmpvest[i] = i;
	j = 0;
	k = 1;
	while(k < n)
	{
		W = E[j].w;
		sn1 = vest[E[j].st]; sn2 = vest[E[j].ed];
	    if(sn1!=sn2)
		{
			k++;MSW += W;
			J = j+1;
			for(i = 0; i < n; i++)
				if(tmpvest[i]==sn2)
					tmpvest[i] = sn1;
			while(J<m&&E[J].w==W)
			{
				if(vest[E[J].st]!=vest[E[J].ed]&&tmpvest[E[J].st]==tmpvest[E[J].ed])
					goto end;
				J++;
			}
	   	    for(i = 0; i < n; i++)
				if(vest[i]==sn2)
					vest[i] = sn1;
		}
		j++;
	}
	printf("%d\n",MSW);
	return ;
	end: printf("Not Unique!\n");
}

void input()
{
	int i, t, st, ed;

	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		for(i = 0; i < m; i++)
		{
			scanf("%d%d%d",&st,&ed,&E[i].w);
			E[i].ed = ed-1;E[i].st = st-1;
		}
		qsort(E,m,sizeof(E[0]),cmp);
		kruskal();
	}
}

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