讨论 / 哪错了,最后一个点过不了,比正解大了0.01
8635722 2010-03-09 03:29:00
点我顶贴 收藏 删除
#include<stdio.h>

#include<math.h>

float a[101][101];

int txt1[101],txt2[101];

float b[101][101];

float max;

float tu[101][101];

int main()

{

int n;

scanf("%d",&n);

int i,j,k;

for(i=1;i<=n;i++)

scanf("%f %f",&a[i][0],&a[i][1]);

for(i=1;i<=n;i++)

for(j=i+1;j<=n;j++)

{

b[i][j]=sqrt((a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(a[i][1]-a[j][1])*(a[i][1]-a[j][1]));

b[j][i]=b[i][j];

}

for(i=2;i<=n;i++)

txt2[i]=1;

txt1[1]=1;

int time=1;

float tmp=0;

int p,q;

for(k=1;k<n;k++)

{

for(i=1;i<=time;i++)

for(j=1;j<=n;j++)

if(txt2[j])

if(b[txt1[i]][j]<tmp||tmp==0)

{

tmp=b[txt1[i]][j];

p=txt1[i];q=j;

}

time++;

txt1[time]=q;

txt2[q]=0;

max+=tmp;

tu[p][q]=tmp;

tu[q][p]=tmp;

tmp=0;

}

tmp=0;

for(k=1;k<n;k++)

{

for(i=2;i<=n;i++)

if(tu[1][i]>0)

{

if(tu[1][i]<tmp||tmp==0)

tmp=tu[1][i];

p=i;

}

if(tu[1][p]>0)

for(i=2;i<=n;i++)

if(tu[p][i]>0)

if(tu[p][i]+tu[1][p]<tu[1][i]||tu[1][i]==0) {tu[1][i]=tu[1][p]+tu[p][i];tu[i][1]=tu[1][i];}

tu[1][p]=-tu[1][p];

tu[p][1]=-tu[p][1];

tmp=0;

}

printf("%0.2f ",max);

printf("%0.2f",-tu[1][n]);

}

#1 txx002@2010-03-09 03:29:00
回复 删除
四舍五入
查看更多回复
提交回复