图论：曼哈顿距离最小生成树

POJ3241：求曼哈顿距离最小生成树上第k大（第n-k小）的边

这么难的建模只能抄下来了

好难啊

给出曼哈顿最小生成树的定义：给定二维平面上的N个点，在两点之间连边的代价为其曼哈顿距离，求使所有点连通的最小代价

显然这个图论题要结合解析几何或者是计算几何的一些东西了

首先给出一个结论：以一个点为原点建立直角坐标系，在每45度内只会向距离该点最近的一个点连边

这种连边方式可以保证边数是O(N)的，那么如果能高效处理出这些边，就可以用Kruskal在O(NlogN)的时间内解决问题

然后给出摘抄dalao的处理方法：

我们只需考虑在一块区域内的点，其他区域内的点可以通过坐标变换“移动”到这个区域内。为了方便处理，我们考虑在y轴向右45度的区域。在某个点A(x0,y0)的这个区域内的点B(x1,y1)满足x1≥x0且y1-x1>y0-x0。
这里对于边界我们只取一边，但是操作中两边都取也无所谓。那么|AB|=y1-y0+x1-x0=(x1+y1)-(x0+y0)。在A的区域内距离A最近的点也即满足条件的点中x+y最小的点。
因此我们可以将所有点按x坐标排序，再按y-x离散，用线段树或者树状数组维护大于当前点的y-x的最小的x+y对应的点（也就是维护区间最小值）。时间复杂度O(NlogN)。 
至于坐标变换，一个比较好处理的方法是第一次直接做(R1==R5)；第二次沿直线y=x翻转，即交换x和y坐标(R2==R6)；第三次沿直线x=0翻转，即将x坐标取相反数(R7==R3)；第四次再沿直线y=x翻转(R8==R4)。
注意只需要做4次，因为边是双向的。

树状数组还可以求区间最值的？？简直爆炸了

算了，直接贴代码了，太难了

  1 #include<cstdio>
  2 #include<algorithm>
  3 using namespace std;
  4 const int maxn=10005;
  5 const int INF=0x7f7f7f7f;
  6 int n,k,cnt,ans,m;
  7 int f[maxn],T[maxn],hs[maxn];
  8 struct Point
  9 {
 10     int x,y,id;
 11     friend bool operator < (const Point &a,const Point &b)
 12     {
 13         return a.x==b.x?a.y<b.y:a.x<b.x;
 14     }
 15 }p[maxn];
 16 struct Data
 17 {
 18     int w,id;
 19     friend bool operator < (const Data &a,const Data &b)
 20     {
 21         return a.w<b.w;
 22     }
 23 }a[maxn];
 24 struct BIT
 25 {
 26     int pos,w;
 27     void init()
 28     {
 29         pos=-1,w=INF;
 30     }
 31 }bit[maxn];
 32 struct Edge
 33 {
 34     int u,v,w;
 35     friend bool operator < (const Edge &a,const Edge &b)
 36     {
 37         return a.w<b.w;
 38     }
 39 }e[maxn<<3];
 40 int lowbit(int x)
 41 {
 42     return x&(-x);
 43 }
 44 int find(int x)
 45 {
 46     return x==f[x]?x:f[x]=find(f[x]); 
 47 }
 48 void kruskal()
 49 {
 50     int tot=0;
 51     sort(e+1,e+cnt+1);
 52     for(int i=1;i<=n;i++) f[i]=i;
 53     for(int i=1;i<=cnt;i++)
 54     {
 55         int fx=find(e[i].u),fy=find(e[i].v);
 56         if(fx!=fy) f[fx]=fy,tot++;
 57         if(tot==k) {ans=e[i].w;break;}
 58     }
 59 }
 60 int query(int x,int m)
 61 {
 62     int M=INF,pos=-1;
 63     for(int i=x;i<=m;i+=lowbit(i))
 64         if(bit[i].w<M) M=bit[i].w,pos=bit[i].pos;
 65     return pos;
 66 }
 67 int dis(int a,int b)
 68 {
 69     return abs(p[a].x-p[b].x)+abs(p[a].y-p[b].y);
 70 }
 71 void update(int x,int M,int pos)
 72 {
 73     for(int i=x;i>=1;i-=lowbit(i))
 74         if(M<bit[i].w) bit[i].w=M,bit[i].pos=pos;
 75 }
 76 void addedge(int u,int v,int w)
 77 {
 78     e[++cnt].u=u;e[cnt].v=v;e[cnt].w=w;
 79 }
 80 void caledge()
 81 {
 82     sort(p+1,p+n+1);
 83     for(int i=1;i<=n;i++) T[i]=hs[i]=p[i].y-p[i].x;
 84     sort(hs+1,hs+n+1);
 85     m=unique(hs+1,hs+n+1)-hs;
 86     for(int i=1;i<=m;i++) bit[i].init();
 87     for(int i=n;i>=1;i--)
 88     {
 89         int x=lower_bound(hs+1,hs+m+1,T[i])-hs+1;
 90         int pos=query(x,m);
 91         if(pos!=-1)
 92             addedge(p[i].id,p[pos].id,dis(i,pos));
 93         update(x,p[i].x+p[i].y,i);
 94     }
 95 }
 96 int main()
 97 {
 98     scanf("%d%d",&n,&k);
 99     k=n-k;
100     for(int i=1;i<=n;i++)
101         scanf("%d%d",&p[i].x,&p[i].y),p[i].id=i;
102     for(int k=1;k<=4;k++)
103     {
104         if(k==2||k==4)
105             for(int i=1;i<=n;i++) swap(p[i].x,p[i].y);
106         else if(k==3)
107             for(int i=1;i<=n;i++) p[i].x=-p[i].x;
108         caledge();
109     }
110     ans=INF;
111     kruskal();
112     printf("%d
",ans);
113     return 0;
114 }