prim.cpp

来自「prim算法：可以从任意结点出发,找出与之相连的最小权值的结点,连接,把连接后的」· C++ 代码 · 共 62 行

#include<stdio.h>
#define infinity 999999999

int main()
{
	long map[101][101],d[101],n,now,next,tot=0;
	bool s[101]={false};int f[101];
	long i,j,k;int t;
        struct
        {int first;
         int end;
         long w;
        }ct[101];
	freopen("prim.in","r",stdin);
	freopen("prim.out","w",stdout);

	scanf("%ld",&n);

	for(i=1;i<=n;i++)
		d[i]=infinity;

	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			scanf("%ld",&map[i][j]);

	now=1;next=1;
	t=0;
	while(next)
	{
		next=0;
		s[now]=true;
		k=infinity;
                t++;
                for(i=1;i<=n;i++)
		{
			if(!s[i]&&d[i]>map[now][i])
			{
				d[i]=map[now][i];
                                f[i]=now;
                        }//if
			if(k>d[i]&&!s[i])
			{
				k=d[i];
				next=i;
                                ct[t].first=f[i];ct[t].end=i;ct[t].w=d[i];
			}//if
		}//for
		now=next;
	}//while

	for(i=2;i<=n;i++)
	{
		tot+=d[i];
	}//for

	printf("%ld\n",tot);
        for (i=1;i<=n-1;i++)
        printf("%d,%d,%ld\n",ct[i].first,ct[i].end,ct[i].w);
	return 0;

}//main