HihoCoder -1097- Minimum Spanning Tree – Prim Algorithm

Minimum spanning tree – Prim algorithm

describe

Recently, sim City, a game that Xiao Hi likes to play, has been released in a new Mod. In this Mod, players can have more than one city!

But, the problem also ensue — little Hi hands now has N cities, and the N cities known between any two cities in the cost of building roads, small Hi want to know, how much the least you can make any two cities can be built by the road to each other (assuming the three cities have A, B, C, If you only need to build roads between AB and BC, then AC can also be connected by these two roads). Note: I don’t know why Prim looks like Dijstra’s algorithm sigma (flying ° д °;). っ.

The input

Each test point (input file) has one and only one set of test data.

In one set of test data:

Line 1 is an integer N, representing the number of cities owned by small Hi.

The next N row is an N*N matrix A, which describes the cost of building A road between any two cities. The JTH number in row I is Aij, representing the cost of building A road between city I and city J.

For 100% of the data, N<=10^3, for any I, Aii=0, for any I, j, Aij=Aji, 0<Aij<10^4.

The output

For each set of test data, an integer Ans is output, representing the minimum construction cost in order for any two cities to be able to reach each other through the constructed roads.

The sample input

    5

0 1005 6963 392 1182

1005 0 1599 4213 1451

6963 1599 0 9780 2789

392 4213 9780 0 5236

1182 1451 2789 5236 0

Sample output

    4178

Program code:

#include<stdio.h>
#include<string.h>
#define inf 0x7f7f7f7f
int e[1010] [1010],book[1010],dis[1010];
int main(a)
{
	int a,n,i,j,count,sumn,minn,u;
	while(scanf("%d",&n)! =EOF) { count=0;
		sumn=0;
		memset(book,0.sizeof(book));
		for(i=1; i<=n; i++)for(j=1; j<=n; j++) {scanf("%d",&a);
				e[i][j]=a;
			}
		for(i=1; i<=n; i++) dis[i]=e[1][i];
		book[1] =1;	
		count++;/ / on behalf of the point
		while(count<n)
		{
			minn=inf;	
			for(i=1; i<=n; i++)if(book[i]==0&&dis[i]<minn)
				{
					minn=dis[i];
					u=i;
				}
			book[u]=1;
			count++;
			sumn+=dis[u];
			for(i=1; i<=n; i++)if(book[i]==0&&dis[i]>e[u][i])
					dis[i]=e[u][i];		
		}	
		printf("%d\n",sumn);
	}
	return 0;
}
Copy the code