苏中建设 官方网站,中国进入全国紧急状态,杭州网站建设网站制作,五大类型网站Time Limit: 1 s Memory Limit: 128 MBProblem Description31世纪#xff0c;人类世界的科技已经发展到了空前的高度#xff0c;星际移民#xff0c;星际旅游早已经不再是问题。人类已经掌握了开发星系的能力。但是#xff0c;无论发展到何种地步#xff0c;资源一直…Time Limit: 1 s Memory Limit: 128 MBProblem Description31世纪人类世界的科技已经发展到了空前的高度星际移民星际旅游早已经不再是问题。人类已经掌握了开发星系的能力。但是无论发展到何种地步资源一直是人们关注的重点。一种新的能源被人类掌握通过它可以搭建虫洞实现超光年传输。发展武器。但是虽然这种物质在宇宙海量的存在着但它对于宇宙的稳定是至关重要的若过量消耗这种物质对于宇宙的稳定星系与星系之间以及星系内部的微妙平衡都会产生巨大的影响。这种物质就是暗物质。-----《宇宙百科》节选现在你所在的星系下有nn个主星球居住着人民。为了星系内部的稳定与和平发展现在需要在nn个主星球之间建立空间虫洞众所周知建立虫洞要消耗大量的暗物质因此你想要在nn个主星球之间建立联系的情况下尽量少的消耗暗物质。目前你已经知道的是建立虫洞所需要消耗的暗物质与两个星球之间的距离成正比,比例系数为kk。并且两个星球之间的距离为空间缩点距离。每个星球有它自己的三维物理坐标。不过现在有一个好消息。你所在的星系掌握了一项新的技术空间奇点压缩简单来说就是降维但是由于技术发展初期不够成熟只能压缩一维。并且任意两个主星球之间都可以选择是否进行空间奇点压缩。现在你想知道在这n个主星球之间建立连接需要花费的最少暗物质是多少。空间缩点距离:设两个nn维坐标a(x1,x2,x3,,,,xn),b(y1,y2,y3,y4,,,yn)a(x1,x2,x3,,,,xn),b(y1,y2,y3,y4,,,yn).设距离为ss则sabs((x1x2x3…xn)−(y1y2y3…yn))sabs((x1x2x3…xn)−(y1y2y3…yn));----以上内容纯属瞎扯请忽略其真实性Input第一行两个整数nn和kk。(1≤n≤105,1≤k≤103)(1≤n≤105,1≤k≤103)接下开nn行每行三个整数x,y,zx,y,z其中第ii行表示第ii个星球在星系中的物理坐标。数据保证没有两个星球处于同一个位置上。(1≤x,y,z≤106)(1≤x,y,z≤106)Outputnn个主星球之间建立连接需要花费的最少暗物质。Sample Input3 21 1 61 2 93 20 8Sample Output4Hint样例说明星球1和星球2之间压缩第三维星球2和星球3之间压缩第二维题解通过排序找出不压缩、压缩X、压缩Y、压缩Z四种情况中相邻最近的两点然后算出压缩后折算的距离并记录下来然后再次排序依次枚举直到连接完所有点连接边长度的总和即为总距离,从而求出所需的暗物质#include#include#include#define maxn 100007using namespace std;int n,k,cnt;int f[maxn];struct sta{int x,y,z,id;}s[maxn];struct P{int st,ed,dis;bool operatorreturn dis}}p[maxn*4];bool xyz(sta a,sta b){return a.xa.ya.z}bool xy(sta a,sta b){return a.xa.y}bool yz(sta a,sta b){return a.ya.z}bool xz(sta a,sta b){return a.xa.z}void init(){cnt0;sort(s,sn,xyz);for(int i1;ip[cnt]{s[i].id,s[i-1].id,s[i].xs[i].ys[i].z-(s[i-1].xs[i-1].ys[i-1].z)};sort(s,sn,xy);for(int i1;ip[cnt]{s[i].id,s[i-1].id,s[i].xs[i].y-(s[i-1].xs[i-1].y)};sort(s,sn,yz);for(int i1;ip[cnt]{s[i].id,s[i-1].id,s[i].ys[i].z-(s[i-1].ys[i-1].z)};sort(s,sn,xz);for(int i1;ip[cnt]{s[i].id,s[i-1].id,s[i].xs[i].z-(s[i-1].xs[i-1].z)};sort(p,pcnt);}int find(int x){return f[x](xf[x]?x:find(f[x]));}void kruskal()//找寻n个点连接的n-1条边的最小和(最小生成树){for(int i0;in;i)f[i]i;int ans0,numn-1;//n-1条树枝for(int i0;i{int afind(p[i].st);int bfind(p[i].ed);if(a!b){f[a]b;num--;ansp[i].dis;}}printf(%d\n,ans*k);}int main(){scanf(%d%d,n,k);for(int i0;iscanf(%d%d%d,s[i].x,s[i].y,s[i].z),s[i].idi1;init();kruskal();return 0;}
