题目链接
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()); } }转载于:https://www.cnblogs.com/Dup4/p/9433129.html
相关资源：JAVA上百实例源码以及开源项目