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 |
用prim过了,Krustra就WA 5555~~~~通过本次实验,我掌握了MST算法。 K版本:(WA)怎么回事? #include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<string.h> using namespace std; #define MAXN 110 float x[MAXN],y[MAXN],z[MAXN],r[MAXN]; float dd[MAXN*MAXN]; int p[MAXN*MAXN]; int cmp(const int x,const int y){return dd[x]<dd[y];} int find(int x) { if(x == p[x]) return x; return find(p[x]); } int main() { int num=0; int edge=0; int v[MAXN*MAXN]; int u[MAXN*MAXN]; int rr[MAXN*MAXN]; float total = 0; while(scanf("%d",&num)!=EOF) { if(!num) break; edge = 0; total = 0; memset(dd,0,sizeof(dd)); for(int i=0;i<num;i++) scanf("%f %f %f %f",&x[i],&y[i],&z[i],&r[i]); for(int i=0;i<num;i++) for(int j=i+1;j<num;j++) { dd[edge] = (float)(sqrt( pow(x[i]-x[j],2)+pow(y[i]-y[j],2)+pow(z[i]-z[j],2)) - r[i] -r[j]); u[edge] = i; v[edge] = j; if(dd[edge]<0) dd[edge] = (float)0; edge++; } for(int i=0;i<edge;i++) rr[i] = i; sort(rr,rr+edge,cmp); for(int i=0;i<edge;i++) p[i] = i; for(int i=0;i<edge;i++) { int bian=rr[i]; int uroot = find(u[bian]); int vroot = find(v[bian]); if(uroot != vroot) { total+=dd[bian]; p[uroot]=vroot; } } printf("%0.3lf\n",total); } return 0; } P:AC了 #include<iostream> #include<cstdio> #include<cmath> #include<string> using namespace std; #define MAXN 110 int main() { int num; float dd[MAXN][MAXN]; float d[MAXN]; bool flag[MAXN]; float x[MAXN],y[MAXN],z[MAXN],r[MAXN]; float total=0; while(scanf("%d",&num)!=EOF) { if(!num) break; memset(flag,false,sizeof(flag)); for(int i=0;i<num;i++) d[i]=10000; total =0 ; for(int i=0;i<num;i++) scanf("%f %f %f %f",&x[i],&y[i],&z[i],&r[i]); for(int i=0;i<num;i++) for(int j=0;j<num;j++) { dd[i][j] = (float)(sqrt( pow(x[i]-x[j],2)+pow(y[i]-y[j],2)+pow(z[i]-z[j],2)) - r[i] -r[j]); if(dd[i][j]<0) dd[i][j] = (float)0; //cout<<dd[i][j]<<endl; } d[0] = 0; for(int i=0;i<num;i++) { double min = 10000; int mark; for(int j=0;j<num;j++) { if(!flag[j] && d[j]<=min) { min = d[j]; mark = j; } } flag[mark] = true; total+=d[mark]; for(int j=0;j<num;j++) { if(!flag[j] && dd[mark][j] < d[j]) d[j] = dd[mark][j]; } } printf("%0.3lf\n",total); } return 0; } /************ 3 10.000 10.000 50.000 10.000 40.000 10.000 50.000 10.000 40.000 40.000 50.000 10.000 2 30.000 30.000 30.000 20.000 40.000 40.000 40.000 20.000 5 5.729 15.143 3.996 25.837 6.013 14.372 4.818 10.671 80.115 63.292 84.477 15.120 64.095 80.924 70.029 14.881 39.472 85.116 71.369 5.553 0 ************/ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator