| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贴一下AC代码-63ms第一次交由于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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator