题目：http://poj.org/problem?id=3241
题意：平面中给定n个点，任意两点之间的距离为它们的哈夫曼距离，求n个点的最小生成树中的第k大边
思路：kuangbin大神的模板，看了好久。。。这个不错：点这里
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <vector> #include <cmath> using namespace std; typedef long long ll; const int N = 100010; const int INF = 0x3f3f3f3f; struct node { int x, y, id; }p[N]; struct edge { int v, u, d; }g[N]; struct BIT { int minn, pos; void init() { minn = INF, pos = -1; } }bit[N]; int n, k, tot; int par[N]; bool cmp(node a, node b) { if(a.x != b.x) return a.x < b.x; else return a.y < b.y; } int ask(int i, int m) { int minn = INF, pos = -1; while(i <= m) { if(bit[i].minn < minn) minn = bit[i].minn, pos = bit[i].pos; i += i & -i; } return pos; } void update(int i, int val, int pos) { while(i > 0) { if(val < bit[i].minn) bit[i].minn = val, bit[i].pos = pos; i -= i & -i; } } void add_edge(int v, int u, int d) { g[tot].v = v, g[tot].u = u, g[tot++].d = d; } void mmst(int n, node p[]) { int a[N], b[N]; tot = 0; for(int i = 0; i < 4; i++) { if(i == 1 || i == 3) { for(int j = 0; j < n; j++) swap(p[j].x, p[j].y); } else if(i == 2) { for(int j = 0; j < n; j++) p[j].x = -p[j].x; } sort(p, p + n, cmp); for(int j = 0; j < n; j++) a[j] = b[j] = p[j].y - p[j].x; sort(b, b + n); int m = unique(b, b + n) - b; for(int j = 1; j <= m; j++) bit[j].init(); for(int j = n - 1; j >= 0; j--) { int pos = lower_bound(b, b + m, a[j]) - b + 1;//按照y-x离散数据 int ans = ask(pos, m); //查询[pos, m]中x+y最小值的编号 if(ans != -1) add_edge(p[j].id, p[ans].id, abs(p[j].x - p[ans].x) + abs(p[j].y - p[ans].y)); update(pos, p[j].x + p[j].y, j); //更新 } } } bool cmpg(edge a, edge b) { return a.d < b.d; } int ser(int x) //并查集查询 { int r = x, i = x, j; while(r != par[r]) r = par[r]; while(par[i] != r) j = par[i], par[i] = r, i = j; return r; } int solve(int k) { mmst(n, p); //预处理，曼哈顿距离最小生成树 for(int i = 0; i < n; i++) par[i] = i; //并查集初始化 sort(g, g + tot, cmpg); //按边的权值排序 for(int i = 0; i < tot; i++) //kruskal算法求最小生成树，因为从小到大，所以求到第n-k小的边就是答案 { int fv = ser(g[i].v), fu = ser(g[i].u); if(fv != fu) { par[fu] = fv; if(--k == 0) return g[i].d; } } } int main() { while(~ scanf("%d%d", &n, &k)) { for(int i = 0; i < n; i++) scanf("%d%d", &p[i].x, &p[i].y), p[i].id = i; printf("%d\n", solve(n - k)); } return 0; }
