蒟蒻求问 算法有啥问题

回复帖子 返回题目

@ Redstone红石粉 2017-08-13 17:47

蒟蒻求问 算法有问题么。。? 最小生成树中 求第n-s小的边的大小。。

不知道哪里有问题。。。求教 谢谢!

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
typedef double db;
const int maxn = 500 + 10;
db x[maxn],y[maxn],f[maxn],last;
int vis[maxn][maxn];
int n,s;
struct node{db w; int a,b;} e[maxn*maxn]; //边e  w权值  a b两端点 
int cmp(node p,node q){return p.w < q.w;}
db calc(int a,int b){return sqrt(pow(x[a]-x[b],2) + pow(y[a]-y[b],2));} //距离公式 
int find(int x){return x==f[x] ? x : f[x]=find(f[x]);} //并查集 
void init_f(){for(int i=1;i<=n;i++)f[i]=i;} //并查集 
void init_e(){  //构建边 
    for(int i=1,p=0;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(!vis[i][j]){ 
                vis[i][j]=vis[j][i]=1;
                e[++p].a=i; e[p].b=j; e[p].w=calc(i,j);
            }
}
void Kruskal(){
    sort(e+1,e+n+1,cmp);
    for(int i=1,cnt=0;cnt<=n-s && i<=n;i++){
        int x=find(e[i].a), y=find(e[i].b);
        if(x!=y){
            cnt++;
            f[x]=y;
            last = e[i].w;
        }
    }
}
int main(){
    scanf("%d%d",&s,&n); 
    for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
    init_e();
    init_f();
    Kruskal();
    printf("%.2lf",e[1].w);
    return 0;
}
@ Redstone红石粉 2017-08-13 17:49 回复

修改 最后输出的“e[1].w” 改为last 。。。。 汗

还有什么问题么。。。还是WA