该算法的思想是分成两个集合，，，，一个为V，，，另一个是U-v，，，从其中一个点开始，，，，标记为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\n");*/
}
}
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\n",s);
}
}