就是莫队的模板题
/* Memory: 0 KB Time: 1663 MS Language: C++11 4.8.2 Result: Accepted */ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cstdlib> #include<cmath> using namespace std; typedef long long LL; const int INF=0x3f3f3f3f; const int maxn=100005; struct Point { int x,y,id; bool operator<(const Point &e)const { if(x==e.x)return y<e.y; return x<e.x; } } point[maxn]; struct Edge { int u,v,w; bool operator<(const Edge &e)const { return w<e.w; } } edge[maxn*4]; int tot; void addedge(int u,int v,int w) { ++tot; edge[tot].u=u; edge[tot].v=v; edge[tot].w=w; } struct Node { int minval,pos; void init() { minval=INF; pos=-1; } } node[maxn]; int lowbit(int x) { return x&(-x); } void update(int i,int val,int pos) { while(i>0) { if(val<node[i].minval) { node[i].minval=val; node[i].pos=pos; } i-=lowbit(i); } } int query(int i,int m) { int minval=INF,pos=-1; while(i<=m) { if(node[i].minval<minval) { minval=node[i].minval; pos=node[i].pos; } i+=lowbit(i); } return pos; } int dis(Point a,Point b) { return abs(a.x-b.x)+abs(a.y-b.y); } int c[maxn],b[maxn],n; void build() { sort(point+1,point+n+1); for(int i=1; i<=n; ++i) b[i]=c[i]=point[i].y-point[i].x; sort(c+1,c+1+n); int m=unique(c+1,c+1+n)-(c+1); for(int i=1; i<=m; ++i) node[i].init(); for(int i=n; i>0; --i) { int pos=lower_bound(c+1,c+1+m,b[i])-c; int tt=query(pos,m); if(tt!=-1)addedge(point[i].id,point[tt].id,dis(point[i],point[tt])); update(pos,point[i].x+point[i].y,i); } } int fa[maxn]; int find(int x) { if(x==fa[x])return x; return fa[x]=find(fa[x]); } LL solve() { sort(edge+1,edge+1+tot); for(int i=1; i<=n; ++i) fa[i]=i; int cnt=0; LL mst=0; for(int i=1; i<=tot; ++i) { int fx=find(edge[i].u); int fy=find(edge[i].v); if(fx==fy)continue; fa[fy]=fx; mst+=edge[i].w; cnt++; if(cnt>=n)break; } return mst; } int main() { int cas=0; while(~scanf("%d",&n),n) { tot=0; for(int i=1; i<=n; ++i) scanf("%d%d",&point[i].x,&point[i].y),point[i].id=i; build(); for(int i=1; i<=n; ++i) point[i].y=-point[i].y; build(); for(int i=1; i<=n; ++i) point[i].y=-point[i].y,swap(point[i].x,point[i].y); build(); for(int i=1; i<=n; ++i) point[i].y=-point[i].y; build(); printf("Case %d: Total Weight = %lld ",++cas,solve()); } return 0; }