注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Poj3241】【曼哈顿距离MST】【Object Clustering】  

2014-03-25 08:59:36|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   题目大意:给你平面上的N个点,将它们分成k个集合,然后每个集合的每个点都至少有一个点使得它们之间的距离不大于X,求最小的X。
    考虑求曼哈顿距离的MST,然后第K大的边就是答案。为什么呢?
    构造出一个解就可以了嘛...实际上咱们把前K-1大边都切掉就可以了,那么接下来显然每一个集合都有一个点使得它们的距离不大于X(因为都在生成树上),然后证明这是底线了,假设还有一种分配方法,那么咱们就可以构造出一棵更小的曼哈顿MST!所以矛盾了。
    接下来就是曼哈顿MST了。关于这个的求法,可以看   曼哈顿MST
   【Poj3241】【曼哈顿距离MST】【Object Clustering】 - z55250825 - z55250825
     只讲讲R1区域如何求。设S为(x0,y0),R1处有一个点为(x1,y1),那么首先要满足在R1区域,得有:
     x1>=x0&&y1>=y0=>y1-x1>=y0-x0
     而 距离应该是  (y1+x1)-(y0+x0) ,要求这个最小实际上就是要求 (y1+x1)最小,而这个最小咱们可以用一个线段树来求,咱们以 yi-xi 为区间的点,然后yi-xi的点的值为所有满足yi-xi的点中xi+yi的最小值,然后为了保证当前询问x0的时候有所有的x>=x0,咱们对于所有的点排序然后倒着处理,然后每扫到一个(x0,y0)先从线段树中查找(x0~n)的最小值,然后把这两个点连边,然后再把这个x0+y0看能否插入到y0-x0中去。
     (ps:这里的y0-x0可能很大,所以需要离散化一下,其实这样子的话就可以离散化之后倒过来,然后就可以用树状数组求1~y0-x0的最小值了,这个应该是最痛快的....)
     然后对于R2区域,只需要对称一个,即x=y,y=x即可,再求一次即可。
     然后对于R7区域,只需要在上一个基础上x=-x,再求一次即可。
     然后对于R8区域,只需要在上一个基础上x=y,y=x,再求一次即可。
     然后就没了。
     咱这里就是直接写树状数组版本的了。(比起分块来这个略DT...不过一次AC还是非常囧的)

     话说写完这个之后就是直接遍历答案了么??感觉略难写233.....还是分块好....
=================================

const maxn=10010; type edge=record x,y,w:longint; end; arr=array[0..maxn]of longint; var e:array[0..maxn*6]of edge; tot:longint; x,y,st,w,c,f,sta:array[0..maxn]of longint; n,k,top:longint; {并查集部分} function getfather(u:longint):longint; begin if f[u]=u then exit(u); f[u]:=getfather(f[u]); exit(f[u]); end; {树状数组部分} procedure insert(i,q,n:longint); begin while i<=n do begin if x[c[i]]+y[c[i]]>x[q]+y[q] then c[i]:=q; i:=i+(i and (-i)); end; end; function ask(i:longint):longint; begin ask:=0; while i>0 do begin if x[ask]+y[ask]>x[c[i]]+y[c[i]] then ask:=c[i]; i:=i-(i and (-i)); end; end; {快排两个} procedure qsort(l,r:longint;var x,y,z:arr;f:boolean); var i,j,u,v,w:longint; begin i:=l;j:=r; u:=x[(l+r)shr 1]; v:=y[(l+r)shr 1]; repeat while (x[i]>u)or((x[i]=u)and(y[i]>v)) do inc(i); while (x[j]<u)or((x[j]=u)and(y[j]<v)) do dec(j); if i<=j then begin w:=x[i];x[i]:=x[j];x[j]:=w; if f then begin w:=y[i];y[i]:=y[j];y[j]:=w; w:=z[i];z[i]:=z[j];z[j]:=w; end; inc(i);dec(j); end; until i>j; if i<r then qsort(i,r,x,y,z,f); if j>l then qsort(l,j,x,y,z,f); end; procedure qsort(l,r:longint); var i,j,x:longint;y:edge; begin i:=l;j:=r; x:=e[(l+r)shr 1].w; repeat while e[i].w<x do inc(i); while e[j].w>x do dec(j); if i<=j then begin y:=e[i];e[i]:=e[j];e[j]:=y; inc(i);dec(j); end; until i>j; if i<r then qsort(i,r); if j>l then qsort(l,j); end; {离散化的二分查找} function find(x,n:longint):longint; var l,r,mid:longint; begin l:=1;r:=n; while l<r do begin mid:=(l+r)shr 1; if w[mid]=x then exit(mid); if w[mid]>x then l:=mid+1 else r:=mid-1; end; exit(l); end; {这里是对一个区域处理的过程} procedure prepare; var i,j,sum:longint; begin fillchar(c,sizeof(c),0); qsort(1,n,x,y,st,true); for i:=1 to n do w[i]:=y[i]-x[i]; qsort(1,n,w,w,w,false); sum:=1; for i:=2 to n do if w[i]<>w[sum] then begin inc(sum); w[sum]:=w[i]; end; for i:=1 to n do begin j:=ask(find(y[i]-x[i],sum)); insert(find(y[i]-x[i],sum),i,sum); if j=0 then continue; inc(tot); e[tot].x:=st[i]; e[tot].y:=st[j]; e[tot].w:=(y[j]+x[j])-(x[i]+y[i]); end; end; {总过程} procedure init; var i,j,u,v:longint; begin read(n,k); for i:=1 to n do begin read(x[i],y[i]); st[i]:=i; end; tot:=0;x[0]:=1<<20;y[0]:=1<<20; prepare;{第一次处理} for i:=1 to n do begin j:=x[i];x[i]:=y[i];y[i]:=j;{交换x,y} end; prepare;{第二次处理} for i:=1 to n do x[i]:=-x[i];{x=-x} prepare;{第三次处理} for i:=1 to n do begin j:=x[i];x[i]:=y[i];y[i]:=j; {交换x,y二周目} end; prepare;{第四次处理} qsort(1,tot); for i:=1 to n do f[i]:=i; top:=0; for i:=1 to tot do begin u:=getfather(e[i].x); v:=getfather(e[i].y); if u=v then continue; inc(top); f[u]:=v; sta[top]:=e[i].w; if top=n-1 then break; end; write(sta[top-k+1]); end; begin init; end.
  评论这张
 
阅读(39)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017