本文共 1292 字，大约阅读时间需要 4 分钟。
给出三维坐标系下的n个球体，求把它们联通的最小代价。
最小生成树加上一点计算几何。建图，若两球体原本有接触，则边权为0；否则边权为它们球心的距离-两者半径之和。这样来跑Prim就ok了。注意精度。
#include #include #include #include #include #include #include #include #include #define rep(i,e) for(int i=0;i<(e);i++)#define rep1(i,e) for(int i=1;i<=(e);i++)#define repx(i,x,e) for(int i=(x);i<=(e);i++)#define X first#define Y second#define PB push_back#define MP make_pair#define mset(var,val) memset(var,val,sizeof(var))#define scd(a) scanf("%d",&a)#define scdd(a,b) scanf("%d%d",&a,&b)#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)#define pd(a) printf("%d\n",a)#define scl(a) scanf("%lld",&a)#define scll(a,b) scanf("%lld%lld",&a,&b)#define sclll(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)#define IOS ios::sync_with_stdio(false);cin.tie(0)#define lc idx<<1#define rc idx<<1|1#define rson mid+1,r,rc#define lson l,mid,lcusing namespace std;typedef long long ll;template void test(T a) { cout< < void test(T a,T2 b) { cout< <<" "<< void test(T a,T2 b,T3 c) { cout< <<" "<<<" "< < lowc[j]){ minc=lowc[j]; p=j; } } ans+=minc; vis[p]=true; for(int j=0;j eps){ lowc[j]=g[p][j]; } } } printf("%.3f\n",ans); } return 0;}
转载于:https://www.cnblogs.com/fht-litost/p/9349776.html