Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴一下AC代码-63ms

Posted by 15211160230 at 2016-08-19 19:48:46 on Problem 3625
第一次交由于sqrt函数不知为什么会编译错误,稍微调整了一下
#include <stdio.h>
#include <math.h>
#define MAXN 1001
#define INF 100000000.0
#define To2(x)	(x)*(x)
typedef struct
{	double x,y;
}Point;
Point vex[MAXN];
double G[MAXN][MAXN];
int vexnum;
double fach(int i,int j)
{
	return (double)sqrt((double)(To2(vex[i].x-vex[j].x)+To2(vex[i].y-vex[j].y)));
}
void Initial(int N)
{	int i,j;
	for(i=1;i<=N;++i)
		for(j=1;j<=i;++j)
			G[i][j]=G[j][i]=fach(i,j);
	vexnum=N;
}
double dis[MAXN];
int visited[MAXN];
int FindMin()
{	int i,k=-1;
	double min=INF;
	for(i=1;i<=vexnum;++i)
	{	if(visited[i]==1)	continue;
		if(min>dis[i])
			k=i,min=dis[i];
	}
	return k;
}
double Prim(int k)
{	int i,j;
	double lowcost=0;
	for(i=1;i<=vexnum;++i)
		visited[i]=0,dis[i]=G[k][i];
	visited[k]=1,dis[k]=0;
	for(i=1;i<vexnum;++i)
	{	k=FindMin();
		if(k==-1)	break;
		visited[k]=1;
		lowcost+=dis[k];
		for(j=1;j<=vexnum;++j)
		{	if(visited[j]==1)	continue;
			if(dis[j]>G[k][j])
				dis[j]=G[k][j];
		}
	}
	return lowcost;
}
int main()
{	int N,M,i;
	int a,b;
	while(scanf("%d %d",&N,&M)!=EOF)
	{	for(i=1;i<=N;++i)
			scanf("%lf %lf",&vex[i].x,&vex[i].y);
		Initial(N);
		while(M--)
		{	scanf("%d %d",&a,&b);
			G[a][b]=G[b][a]=0;
		}
		printf("%.2lf\n",Prim(1));
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator