省赛复习(3) 最小生成树专题

P8074 [COCI2009-2010#7] SVEMIR 要求出min{|x_A-x_B|,|y_A-y_B|,|z_A-z_B|}，数量级为1e5，若是两两相连，等差数列为n*(n-1)/2肯定会MLE，超出内存。 因此，注意边长间的关系。当两个点x距离很近时，表达式得到的值最小，同理y,z也是。因此会想到排三次序，每次排序连接相邻的两个点,数量级为最大为3e5. kruskral算法的复杂度O(e*loge), prim算法的复杂度为O(n*n)，可脱离边。 prim算法复杂度为O(n*loge),还是无法脱离边 因此，kruskral算法对于稀疏图最佳,prim算法用于稠密图最佳。

#include 
#define endl '\n'
#define ll long long
#define pb push_back
using namespace std;
const int N=5e5+5;
int n,f[N],cnt,ans;
struct node
{
    int x,y,z,id;
}e[N];
bool cmp1(node e1,node e2)   {return e1.x