Hdu3405 World Islands解题报告.docVIP

Hdu3405 World Islands /* Author: yuanchuanshun Date: 28-05-10 20:29 Description: 解题报告 */ 题目大意及分析 /showproblem.php?pid=3405 典型的求最小生成树，给定个数的岛，其中除却一个岛不与其他岛相连，其余皆相连且要求相连所用网线距离和最短。 起初的想法是求出一个最小生成树后，再寻找边上最小的叶剪去，（不过实现这个想法也是有点难度，我下面给出了当时的源码）结果提交错误，之后就换了想法，循环去掉每个点，求其余点的最小生成树，且题目数据最多50，完全可以枚举。 二、代码 #includestdio.h #includemath.h #define MAX 100000000 double dis[52],a[52][52],flag[52],x[52],y[52],sum[52]; int TT; double DIS(double c,double d,double a,double b) { return sqrt((a-c)*(a-c)+(b-d)*(b-d)); } void prime(double *c,double *d,int n) { int i,j,k,time; double min,max,SUM; for(i=1;i=n;i++) { flag[i]=0; dis[i]=MAX; } flag[1]=1; for(i=2;i=n;i++) { dis[i]=DIS(c[1],d[1],c[i],d[i]); a[1][i]=a[i][1]=dis[i]; } for(i=2;in;i++) for(j=i+1;j=n;j++) { a[i][j]=a[j][i]=DIS(c[i],d[i],c[j],d[j]); } SUM=0; for(time=1;timen;time++) { min=MAX; for(i=2;i=n;i++) { if(flag[i]==1) continue; if(mindis[i]) { min=dis[i]; k=i; } } SUM+=min; flag[k]=1; for(j=1;j=n;j++) { if(flag[j]==1) continue; double t=MAX; //int t; for(k=1;k=n;k++) { if(flag[k]==0) continue; if(a[k][j]t) t=a[k][j]; } dis[j]=t; } } sum[++TT]=SUM; } int main() { int T,N,i,j,k; double Temp,xx[52],yy[52]; scanf(%d,T); while(T--) { TT=0; Temp=MAX; scanf(%d,N); for(i=1;i=N;i++) scanf(%lf%lf,x[i],y[i]); for(i=1;i=N;i++) { k=1; for(j=1;j=N;j++) { if(i==j)continue; //xx[++k]=x[j]; //yy[++k]=x[j]; //以后最好别放这种低级错误。 xx[k]=x[j]; yy[k]=y[j]; k++; } prime(xx,