首页 > 代码库 > POJ 3241 Object Clustering 曼哈顿距离最小生成树
POJ 3241 Object Clustering 曼哈顿距离最小生成树
题目大意:求出曼哈顿距离最小生成树上的第k大边权。
思路:首先,你要了解:http://blog.csdn.net/acm_cxlove/article/details/8890003
也就是说,我们以每一个点为中心,把平面分成8个部分,每一个部分我们只需要离这个点最近的点。然后加上建一条边连接这个边和最近的点。然后就是MST。
听说这个算法是莫队算法的基础,我现在就去学。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 10010 #define INF 0x3f3f3f3f using namespace std; struct Edge{ int x,y,length; bool operator <(const Edge &a)const { return length < a.length; } Edge(int _,int __,int ___):x(_),y(__),length(___) {} Edge() {} }edge[MAX << 3]; struct Point{ int x,y,_id; bool operator <(const Point &a)const { if(x == a.x) return y < a.y; return x < a.x; } void Read() { scanf("%d%d",&x,&y); } }point[MAX]; int points,k,edges; int fenwick[MAX]; pair<int,int *> xx[MAX]; int y_x[MAX]; int father[MAX]; inline int CalcM(const Point &a,const Point &b) { return abs(a.x - b.x) + abs(a.y - b.y); } inline int GetPos(int x) { int re = 0; for(; x <= points; x += x&-x) if(point[fenwick[x]].x + point[fenwick[x]].y < point[re].x + point[re].y) re = fenwick[x]; return re; } inline void Fix(int x,int pos) { for(; x; x -= x&-x) if(point[fenwick[x]].x + point[fenwick[x]].y > point[pos].x + point[pos].y) fenwick[x] = pos; } void MakeGraph() { for(int dir = 1; dir <= 4; ++dir) { if(dir == 2 || dir == 4) for(int i = 1; i <= points; ++i) swap(point[i].x,point[i].y); if(dir == 3) for(int i = 1; i <= points; ++i) point[i].y *= -1; sort(point + 1,point + points + 1); memset(fenwick,0,sizeof(fenwick)); for(int i = 1; i <= points; ++i) xx[i] = make_pair(point[i].y - point[i].x,&y_x[i]); sort(xx + 1,xx + points + 1); int t = 0; xx[0].first = INF; for(int i = 1; i <= points; ++i) { t += (xx[i].first != xx[i - 1].first); *xx[i].second = t; } for(int i = points; i; --i) { int temp = GetPos(y_x[i]); if(temp) edge[++edges] = Edge(point[i]._id,point[temp]._id,CalcM(point[i],point[temp])); Fix(y_x[i],i); } } } int Find(int x) { if(father[x] == x) return father[x]; return father[x] = Find(father[x]); } int MST() { sort(edge + 1,edge + edges + 1); for(int i = 1; i <= edges; ++i) { int fx = Find(edge[i].x); int fy = Find(edge[i].y); if(fx != fy) { father[fx] = fy; if(!--k) return edge[i].length; } } return 0; } int main() { cin >> points >> k; k = points - k; point[0].x = point[0].y = INF; for(int i = 1; i <= points; ++i) { point[i].Read(); point[i]._id = i; father[i] = i; } MakeGraph(); cout << MST() << endl; return 0; }
POJ 3241 Object Clustering 曼哈顿距离最小生成树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。