[COCI 2009/2010 – Constest #7 SVEMIR]10^5个点的完全图的最小生成树、堆、并差集、暴力解法+求正解~

【题目地址】http://evaluator.hsin.hr/login.php?redirect=index.php
【题目大意】
给定N<=10^5个点，每个点有一个三维坐标(Xi,Yi,Zi)
两个点间的距离定义为Distance=max(|Xi-Xj|，|Yi-Yj|，|Zi-Zj|)。
然后让你求它的最小生成树。
【算法分析】
标题是虽然是事实，但是明显是吓人的。。。。（为啥我也变成标题党了= =）
然后这题我的做法非常暴力。
我的方法如下（由于难以言表，请尽量结合程序围观。。。）：
首先必然的一件事是：用的kruskal  （MS拼错了，谁来纠正一下。。。）
先把点分开三个，分到不同的数组里，分别按x，y，z排序。
然后每个点设置一个已走步长：Lena[i] Lenb[i] Lenc[i]。
再建3个堆。
分别装的key值是类似这种a[i+Lena[i]].x-a[i].x。
然后每次取a,b,c三个堆中key值最小的出来，然后kruskal。
然后再把Lena[i]+1，再次把a[i+Lena[i]].x-a[i].x放入堆中。
（因为这个数肯定是增大了，所以能保证先把小的边弄了。）
最后并差集弄一下，就是一个完整的超暴力kruskal。
【其他】
Test # Score Time Memory Result 1 10 0.00s 9760 kB Correct! 2 10 0.00s 9760 kB Correct! 3 10 0.00s 9760 kB Correct! 4 10 0.00s 9760 kB Correct! 5 10 0.00s 9760 kB Correct! 6 10 0.04s 9920 kB Correct! 7 10 0.31s 9760 kB Correct! 8 10 0.30s 9760 kB Correct! 9 10 0.47s 9760 kB Correct! 10 10 0.80s 9760 kB Correct!
期待众神牛讲出正解。毕竟做人不能那么暴力。
【CODE】
#include #include #include const int N=100005;

struct Heap_Type{
int tot;
struct Node{int pos,key;}d[N],tmp;

void swap(Node &x,Node &y){tmp=x; x=y; y=tmp;}

void up(int k){
while (k>1){
if (d[k].key swap(d[k],d[k/2]);
k/=2;
}else break;
}
}

void down(int k){
int p;
while (k*2<=tot){
p=k*2;
if (p+1<=tot && d[p+1].key if (d[p].key swap(d[p],d[k]);
k=p;
}else break;
}
}

void ins(int key,int pos){
tot++;
d[tot].key=key;
d[tot].pos=pos;
up(tot);
}

void del(){
swap(d[1],d[tot]);
tot–;
down(1);
}
}Heapa,Heapb,Heapc;
struct Point{int x,y,z,pos;}a[N],b[N],c[N];
int n,times;
int F[N],Num[N],Lena[N],Lenb[N],Lenc[N];
long long ans;

int cmpa(const void *x,const void *y){return ((Point*)x)->x-((Point*)y)->x;}
int cmpb(const void *x,const void *y){return ((Point*)x)->y-((Point*)y)->y;}
int cmpc(const void *x,const void *y){return ((Point*)x)->z-((Point*)y)->z;}

void init(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
a[i].pos=i;
c[i]=b[i]=a[i];
Lena[i]=Lenb[i]=Lenc[i]=1;
F[i]=i; Num[i]=1;
}
qsort(a+1,n,sizeof(Point),cmpa);
qsort(b+1,n,sizeof(Point),cmpb);
qsort(c+1,n,sizeof(Point),cmpc);
Heapa.tot=Heapb.tot=Heapc.tot=0;
for (int i=1;i Heapa.ins(a[i+1].x-a[i].x,i);
Heapb.ins(b[i+1].y-b[i].y,i);
Heapc.ins(c[i+1].z-c[i].z,i);
}
}

int GF(int p){
int res=p,tmp;
while (F[res]!=res) res=F[res];
while (p!=res){
tmp=F[p];
F[p]=res;
p=tmp;
}
return res;
}

inline bool set_union(int x,int y){
if (GF(x)==GF(y)) return false;
times++;
if (Num[F[x]] Num[F[y]]+=Num[F[x]];
F[F[x]]=F[y];
}else{
Num[F[x]]+=Num[F[y]];
F[F[y]]=F[x];
}
return true;
}

void solve(){
times=1; ans=0;
int i;
while (times if (Heapa.d[1].key<=Heapb.d[1].key && Heapa.d[1].key<=Heapc.d[1].key){
i=Heapa.d[1].pos;
if (set_union(a[i].pos,a[i+Lena[i]].pos)) ans+=Heapa.d[1].key;
Lena[i]++;
Heapa.del();
if (i+Lena[i]<=n) Heapa.ins(a[i+Lena[i]].x-a[i].x,i);
}else
if (Heapb.d[1].key<=Heapa.d[1].key && Heapb.d[1].key<=Heapc.d[1].key){
i=Heapb.d[1].pos;
if (set_union(b[i].pos,b[i+Lenb[i]].pos)) ans+=Heapb.d[1].key;
Lenb[i]++;
Heapb.del();
if (i+Lenb[i]<=n) Heapb.ins(b[i+Lenb[i]].y-b[i].y,i);
}
else{
i=Heapc.d[1].pos;
if (set_union(c[i].pos,c[i+Lenc[i]].pos)) ans+=Heapc.d[1].key;
Lenc[i]++;
Heapc.del();
if (i+Lenc[i]<=n) Heapc.ins(c[i+Lenc[i]].z-c[i].z,i);
}
}
printf("%lldn",ans);
}

int main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
init();
solve();
}