HDOJ 1162 Realtime Status 这道题我写的lruskal算法代码该怎么优化？谢谢大牛们回答
下面是我的代码，在HDOJ里超时通不过。
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct{
double x,y;
int parent;
}point[105];
struct Edge{
int from,to;
double dis;
}edge[5100];
void init(int n){
for(int i=1;i<=n;i++)
point[i].parent=i;
}
int find(int x){
while(x!=point[x].parent)
x=point[x].parent;
return x;
}
void merge(int x,int y){
x=find(x);
y=find(y);
if(x!=y)
point[x].parent=y;
}
bool compare(Edge a,Edge b){
return a.dis<b.dis;
}
int main(){
int n;
double sum;
while(scanf("%d",&n)){
float a,b;
for(int i=1;i<=n;i++)
scanf("%lf%lf",&point[i].x,&point[i].y);
int p=1;
init(n);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
edge[p].from=i;
edge[p].to=j;
edge[p].dis= sqrt( ((point[i].x-point[j].x)*(point[i].x-point[j].x))+((point[i].y - point[j].y)*(point[i].y - point[j].y)) );
p++;
}
}
sort(edge+1,edge+p,compare);
int m=n*(n-1)/2;
sum=0.0;
for(int i=1;i<=m&&n>1;i++){
int x=find(edge[i].from),y=find(edge[i].to);
if(x!=y){
merge(x,y);
n--;
sum+=edge[i].dis;
}
}
printf("%.2lf\n",sum);
}
return 0;
}
[解决办法]
额..这个怎么成非技术问题了..?
[解决办法]
ACM题最好去算法区问吧
