Building a Space Station

POJ-2031

注意，这里的输出需要是%f型而不是%lf型的，否则wa.

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

const int maxn=101;

int n;

struct node{

    double x;

    double y;

    double z;

    double r;

};

node cell[maxn];

struct edge{

    int from;

    int to;

    double w;

    bool operator<(const edge& t)const{

        return w<t.w;

    }

};

edge edges[5003];

int set[maxn];

int find(int x){

    return x==set[x]?set[x]:set[x]=find(set[x]);

}

double kruskal(int es){

    double sum=0.000;

    for(int i=0;i<n;i++){

        set[i]=i;

    }

    sort(edges,edges+es);

    for(int i=0;i<es;i++){

        int from=edges[i].from;

        int to=edges[i].to;

        double w=edges[i].w;

        int x=find(from);

        int y=find(to);

        if(x!=y){

            //cout<<from<<" "<<to<<" "<<w<<endl;

            set[x]=y;

            sum+=w;

        }

    }

    return sum;

}

int main(){

    while(cin>>n&&n){

        for(int i=0;i<n;i++){

            scanf("%lf%lf%lf%lf",&cell[i].x,&cell[i].y,&cell[i].z,&cell[i].r);

            // cin>>cell[i].x>>cell[i].y>>cell[i].z>>cell[i].r;

        }

        int es=0;//边的数量

        for(int i=0;i<n;i++){

            for(int j=0;j<i;j++){

                double radius=cell[i].r+cell[j].r;//半径之和

                double distance=sqrt((cell[i].x-cell[j].x)*(cell[i].x-cell[j].x)+(cell[i].y-cell[j].y)*(cell[i].y-cell[j].y)+(cell[i].z-cell[j].z)*(cell[i].z-cell[j].z));

                if(distance<=radius)//重叠

                    edges[es].from=i,edges[es].to=j,edges[es++].w=0.000;

                else{

                    edges[es].from=i,edges[es].to=j,edges[es++].w=distance-radius;

                }

                //cout<<distance<<" ";

            }

            //cout<<endl;

        }

    double end=kruskal(es);

    printf("%.3f\n",end);

    }

    return 0;

}

巴特西

POJ-2031(最小生成树+kruskal)

Building a Space Station

POJ-2031

注意，这里的输出需要是%f型而不是%lf型的，否则wa.

最新文章

热门文章