问题描述
- 九度oj 题目1144：Freckles，不能通过，为什么超时间？
-
#include
#include
#include
using namespace std;
const int maxn = 5000;
const double INF = 1000000000;
bool vis[maxn] = {false};
double x[maxn],y[maxn];
int n ;
int father[maxn];
struct Node{
double u,v;
double cost;
}edge[maxn];
int index;
bool cmp(Node a,Node b){
return a.cost<b.cost;
}
void init(){for(int i = 0;i < n;i++){
for(int j = 0;j <= i;j++){
edge[index].u = i;
edge[index].v = j;
edge[index++].cost = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
}
}int findfather(int x){
while(x!=father[x]){
x = father[x];
}
return x;
}double Krustral(){
double ans = 0,num = 0;
for(int i = 0; i< n;i++){
father[i] = i;
}
for(int i = 0; i < index;i++){
int faa = findfather(edge[i].u);
int fab = findfather(edge[i].v);
if(faa!=fab){
father[faa] = fab;
ans+=edge[i].cost;
num++;
if(index-1==num) break;
}
}
return ans;
}int main(){
while(scanf("%d",&n)!=EOF&&n!=0){
index = 0;
fill(x,x+maxn,0);
fill(y,y+maxn,0);
for(int i = 0;i < n;i++){
scanf("%lf %lf",&x[i],&y[i]);
}
init();
sort(edge,edge+index,cmp);
double a = Krustral();
printf("%.2lf
",a);
}
return 0;
}
解决方案
可能是你算法不优化
参考：http://www.ithao123.cn/content-5538295.html
解决方案二：
http://blog.csdn.net/binyuapple/article/details/18942861
解决方案三：
http://www.fx114.net/qa-54-214088.aspx
解决方案四：
九度oj 题目1144：Freckles