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