hdu1879 prim和kruskal两种算法。

//prim看不懂的看看思想就容易懂啦

#include <stdio.h>
#include <string.h>
#define inf 0x3fffffff
int map[101][101],flag[101],minpos[101],n,m,pos;
void prim()
{
	int t,p,min,sum=0;
	minpos[0]=t=1;
	flag[1]=1;
	while(t<n)
	{
		min=inf;
		for(int i=0;i<t;i++)
		{
			p=minpos[i];
			for(int j=1;j<=n;j++)
			if(map[p][j]<min&&!flag[j])
			min=map[p][j],pos=j;
		}
		sum+=min;
		minpos[t++]=pos;
		flag[pos]=1;
	}
	printf("%d\n",sum);
}
int main()
{
	int a,b,cost,aci;
	while(scanf("%d",&n)!=EOF&&n)
	{
		m=n*(n-1)/2;
		memset(flag,0,sizeof(flag));
		memset(map,inf,sizeof(map));
		for(int i=0;i<m;i++)
		{
			scanf("%d %d %d %d",&a,&b,&cost,&aci);
		    if(aci)
		    map[a][b]=map[b][a]=0;
		    else
		    map[a][b]=map[b][a]=cost;
		}
		
		prim();
	}
	return 0;
}#include <stdio.h>
#inclu