最小生成樹
Kruskal
#include#include #include #include using namespace std; struct A{ int x,y; double z; }a[500010]; int r[755]; int find_(int x) { while(x!=r[x]) x=r[x]; return x; } int cmp(A a,A b) { return a.z j){ double s=sqrt( (x[i]-x[j])*(x[i]-x[j])+ (y[i]-y[j])*(y[i]-y[j]) ); a[++k].x=i; a[k].y=j; a[k].z=s; } } scanf("%d",&m); while(m--){ scanf("%d%d",&c,&b); int aa=find_(c); int bb=find_(b); if(aa!=bb){ r[aa]=bb; } } sort(a+1,a+1+k,cmp); double ans=0; for(i=1;i<=k;i++) { int aa=find_(a[i].x); int bb=find_(a[i].y); if(aa!=bb){ r[aa]=bb; ans=ans+a[i].z; } } printf("%.2lf\n",ans); } return 0; }