tunnels.txt

来自「以前ACM在哈工程HRBEU做的一些简单题目」· 文本 代码 · 共 72 行

#include <stdio.h>
#include <math.h>
struct tree
{
	double x,y,dis[100];
}node[100];
int pd(int v[],int j,int t)
{
	int i;
	for(i=0;i<t;i++)
		if(j==v[i])break;
		if(i>=t)return 1;
		return 0;
}

int main()
{
    int n,i,j,t,v[100],k,z,q,n1;
	double sum=0,tot,temp;
	while(scanf("%d",&n))
	{
	  if(n==0)break;
      i=0;
	   while(n--)
	  {
		scanf("%lf%lf",&node[i].x,&node[i].y);
		i++;
	  }
       if(i)
	   {
		   sum=0;
		  for(j=0;j<i-1;j++)
		  for(t=j+1;t<i;t++)
		  {
		 tot=fabs(sqrt((node[j].x-node[t].x)*(node[j].x-node[t].x)+(node[j].y-node[t].y)*(node[j].y-node[t].y)));
		  node[j].dis[t]=tot;
		  node[t].dis[j]=tot;
		   }
		 n1=i-1;
		 t=0;
		 v[t++]=0;
         while(n1--)
		 {
			 for(k=0;k<t;k++)
			 {
				 if(k==0)
				 {
					 q=0;
				 while(pd(v,q,t)==0)q++;
				  temp=node[v[k]].dis[q];
				  z=q;
				 }
			 for(j=0;j<i;j++)
				 if(pd(v,j,t)&&temp>node[v[k]].dis[j]&&node[v[k]].dis[j]!=0)
				 {
					 temp=node[v[k]].dis[j];
					 z=j;
				 }
			 }
			 v[t++]=z;
			 sum+=temp;
			 }
		 printf("%.2lf\n",sum);
	   }
	   
	   }
	return 0;
}