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

Re:只能c++过 我也是醉了

Posted by chaiyinlei at 2017-03-23 02:14:50 on Problem 2031
In Reply To:只能c++过 我也是醉了 Posted by:chaiyinlei at 2017-03-23 02:14:36
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#define inf 0x3f3f3f
double dis[105],lu[105][105],qiu[105][4];;
int vis[105],n;
void prim()
{
	for(int i=1;i<=n;i++)
	{
		dis[i]=lu[1][i];
		vis[i]=0;
	}
	dis[1]=0;vis[1]=1;
	for(int i=2;i<=n;i++)
	{
		double min=inf;
		int p;
		for(int j=1;j<=n;j++)
		{
			if(!vis[j]&&dis[j]<min)
			{
				min=dis[j];
				p=j;
			}
		}
		vis[p]=1;
		for(int j=1;j<=n;j++)
		{
			if(!vis[j]&&dis[j]>lu[p][j])
			dis[j]=lu[p][j];
		}
	}
	double sum=0;
	for(int i=1;i<=n;i++)
	{
	sum+=dis[i];
	}
	printf("%.3lf\n",sum);
}
void qiuti()
{
	double x,y,z,l,r;
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++)
			{
				x=qiu[i][0]-qiu[j][0];
				y=qiu[i][1]-qiu[j][1];
				z=qiu[i][2]-qiu[j][2];
				l=sqrt(x*x+y*y+z*z);
				r=qiu[i][3]+qiu[j][3];
				if(l<=r)                  //小于等于 
				lu[j][i]=lu[i][j]=0;
				else
				lu[j][i]=lu[i][j]=l-r;
			}
		}
}
int main()
{
	while(scanf("%d",&n),n)
	{
		memset(qiu,0,sizeof(qiu));
		int i,j;
		for(i=1;i<=n;i++)
			for(j=i;j<=n;j++)
			lu[i][j]=lu[j][i]=inf;
		for(i=1;i<=n;i++)
		{
			scanf("%lf %lf %lf %lf",&qiu[i][0],&qiu[i][1],&qiu[i][2],&qiu[i][3]);
		}
		qiuti();
	    prim();  
	}
}

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