题目链接

http://poj.org/problem?id=2031

题意

给出N个球形的 个体 如果 两个个体 相互接触 或者 包含 那么 这两个个体之间就能够互相通达 现在给出若干个这样的个体 要求 从一个个体 可以到达任意一个另外的个体 如果两个个体之间 本来是不能够相互通达的 那么可以在这两个个体之间 建一座桥梁 现在要求 满足 从任意一个个体就可以到达任意一个另外的个体 需要建设桥梁的最少花费

思路

因为两个球体之间，如果 两个球心的距离 <= 两个球体的半径之和 那么这两个球体 就是 可以通达的 边权为0 反之 边权 就是 球心距离减去半径之和

然后最小生成树 一下 就可以了 要加入 访问标记 因为 边权为0的 也是需要连通的

然后有一个奇怪的点

POJ 上面 我用G++ 提交 最后输出 要用 %.3f

然后用C++ 提交 就没有问题

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a, b) memset(a, (b), sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = acos(-1.0);

const double E = exp(1.0);

const double eps = 1e-8;

const int INF = 0x3f3f3f3f;

const int maxn = 1e2 + 5;

const int MOD = 1e9 + 7;

struct node

{

    double x, y, z, r;

}q[maxn];

double G[maxn][maxn];

double lowcost[maxn];

int v[maxn];

double cover(node a, node b)

{

    double dis = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));

    if (dis < a.r + b.r || fabs(dis - a.r - b.r) < eps)

        return 0.0;

    return dis - a.r - b.r;

}

int n;

int findMin()

{

    double Min = INF * 1.0;

    int flag = 0;

    for (int i = 1; i <= n; i++)

    {

        if (v[i] == 0 && lowcost[i] < Min)

        {

            Min = lowcost[i];

            flag = i;

        }

    }

    return flag;

}

double prime()

{

    double ans = 0.0;

    for (int i = 1; i <= n; i++)

        lowcost[i] = G[1][i];

    lowcost[1] = 0.0;

    v[1] = 1;

    for (int i = 2; i <= n; i++)

    {

        int k = findMin();

        if (k)

        {

            ans += lowcost[k];

            lowcost[k] = 0.0;

            v[k] = 1;

            for (int j = 1; j <= n; j++)

            {

                if (v[j] == 0 && G[k][j] < lowcost[j])

                    lowcost[j] = G[k][j];

            }

        }

    }

    return ans;

}

int main()

{

    while (scanf("%d", &n) && n)

    {

        CLR(v, 0);

        for (int i = 1; i <= n; i++)

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

        for (int i = 1; i <= n; i++)

        {

            for (int j = i + 1; j <= n; j++)

                    G[i][j] = G[j][i] = cover(q[i], q[j]);

        }

        printf("%.3lf\n", prime());

    }

}