简单最小生成树
#include <iostream> #include <cstring> #include <cmath> #define inf 100000000 using namespace std; int n; double map[250][250],lowc[250]; bool vis[250]; struct node { int x,y; }cell[150]; double dis(node a,node b) { return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double prim() { int i,j,p; double minc,res=0; memset(vis,0,sizeof(vis)); vis[0]=1; for(i=1;i<n;i++) lowc[i]=map[0][i]; for(i=1;i<n;i++) { minc=inf; p=-1; for(j=0;j<n;j++) if(vis[j]==0 && minc>lowc[j]) { minc=lowc[j]; p=j; } if(inf==minc) return -1; if(res<minc) res=minc; if(p==1) break; vis[p]=1; for(j=0;j<n;j++) if(vis[j]==0 && lowc[j]>map[p][j]) lowc[j]=map[p][j]; } return res; } int main() { int i,j,case_t=0,fg=0; double d; while(scanf("%d",&n)!=EOF && n) { if(fg) printf("/n"); fg=1; case_t++; for(i=0;i<n;i++) scanf("%d%d",&cell[i].x,&cell[i].y); for(i=0;i<n;i++) for(j=0;j<n;j++) { map[i][j]=dis(cell[i],cell[j]); } printf("Scenario #%d/n",case_t); printf("Frog Distance = %.3lf/n",prim()); } return 0; }
