保灵 kruskal 求助
查看原帖
保灵 kruskal 求助
399116
LYqwq楼主2022/3/20 17:46

样例输出 0.00,全 WA 求助QwQ

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
template<typename T=int>
inline T read(){
    T X=0; bool flag=1; char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
    if(flag) return X;
    return ~(X-1);
}

const int N=1e6+5;
struct edge{
    int u,v;
    double w;
    bool operator<(edge a){
        return this->w==a.w ? this->u<a.u : this->w<a.w;
    }
}e[N];
int n,m,x[N],y[N],u,v;
int top;

double dis(int x1,int y1,int x2,int y2){
    return sqrt(pow(x1-x2,2)*pow(y1-y2,2));
}

void add(int u,int v,double w){
    top++;
    e[top].u=u;
    e[top].v=v;
    e[top].w=w;
}

template<class T=int>
class set{
    public:
        set(){
            f=new T[N];
            for(int i=0; i<N; i++){
                f[i]=i;
            }
        }
        T find(T x){
            if(f[x]==x) return x;
            return f[x]=find(f[x]);
        }
        void merge(T x,T y){
            f[find(x)]=find(y);
        }
    private:
        T *f;
};

template<typename T=int>
T kruskal(int n,int m){
    sort(e+1,e+m+1);
    set s;
    T ans=0;
    int cnt=1;
    for(int i=1; i<=m; i++){
        if(s.find(e[i].u)!=s.find(e[i].v)){
            ans+=e[i].w;
            s.merge(e[i].u,e[i].v);
            if(++cnt==n){
                break;
            }
        }
    }
    return ans;
}

int main(){
    n=read(),m=read();
    for(int i=1; i<=n; i++){
        x[i]=read(),y[i]=read();
    }
    for(int i=1; i<=n; i++){
        for(int j=i+1; j<=n; j++){
            add(i,j,dis(x[i],y[i],x[j],y[j]));
        }
    }
    for(int i=1; i<=m; i++){
        u=read(),v=read();
        add(u,v,0.0);
    }
    printf("%.2lf\n",kruskal<double>(n,top));
    return 0;
}
2022/3/20 17:46
加载中...