最小生成ツリープリムアルゴリズムHDOJ 1879は引き続きプロジェクトを開通します.

アルゴリズムの考えは、2つのセットに分けられ、、、1つはV、もう1つはU-vであり、その中の1つの点から、、、vとしてマークされ、そして、VとU-Vのすべての点の最短距離を探し出す.この点をVと表記します.これによって類推する.U-Vが空になるまで.
  タイトル接続 http://acm.hdu.edu.cn/showproblem.php?pid=1879
  

#include<stdio.h>
#include<string.h>
#define max 100000
int n,dist[101],st[101][101],vi[101];
void in()
{
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
		{
			st[i][j]=max;
			if(i==j)
				st[i][j]=0;
			
			
		}

}
int prim()
{
	int sum=0,i,ma,fl,j;
	for(i=1;i<=n;i++)
		dist[i]=st[1][i];
	memset(vi,0,sizeof(vi));
	vi[1]=1;
	dist[1]=max;
	for(i=1;i<n;i++)
	{
		ma=max;
		for(j=1;j<=n;j++)
		{
			if(!vi[j]&&dist[j]<ma)
			{
				ma=dist[j];
				fl=j;

			}
		}
		
		vi[fl]=1;
		sum+=dist[fl];
		for(j=1;j<=n;j++)
			if(!vi[j]&&st[fl][j]<dist[j])
			{
				dist[j]=st[fl][j];
				/*printf("fasdfdasf
");*/
			}
	}
	return sum;

}
int main()
{
	while(scanf("%d",&n)&&n)
	{
		int a,c,b,d,s;
		in();
		for(int i=0;i<n*(n-1)/2;i++)
		{
			scanf("%d%d%d%d",&a,&b,&c,&d);
			if(!d)
			st[b][a]=st[a][b]=c;
			else
				st[b][a]=st[a][b]=0;
		}
		s=prim();
		printf("%d
",s);
	}
	
}