2148782_wa.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, mark;
	int vest[101];
	int sn1, sn2, SN1, SN2;
	
	for(i = 0; i < n; i++)
		vest[i] = i;
	j = 0;
	k = 1;
	while(k < n)
	{
		W = E[j].w;
		mark = 0;
		while(E[j].w==W)
		{
			sn1 = vest[E[j].st]; sn2 = vest[E[j].ed];
	    	if(sn1!=sn2)
			{
				SN1 = sn1;
				SN2 = sn2;
				mark++;
			}
			j++;
		}
		if(mark<=1)
		{
			if(mark)
			{
				k++;MSW += E[j-1].w;
	   	    	for(i = 0; i < n; i++)
	    	    	if(vest[i]==SN2)
		    	     	vest[i] = SN1;
			}
		}
	    else
		   	goto end;
	    
	}
	printf("%d\n",MSW);
end: 
	if(mark>1)
		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;
}