|
|
這題很牛逼，是樓教主的《男人七題》的其中一道。
求：一棵樹內最短距離小于K的點對數量
后來看了解題報告，原來樹也是可以分治的。
分：
選取一條邊，將一棵樹分成兩半，這兩半的節點數要盡量相等。
首先，統計個每個節點的下面有多少個節點
然后，就知道每個邊切斷之后的情況了。選擇最優的即可。
治：
分成兩半之后，統計經過該條邊的點對線段中，長度小于K的數目。
Amber 大牛論文的精辟描述如下：
Divide and Conquer.
Each iteration, we should choose an edge (u, v) and divide the tree into two parts disjoined by the edge. Due to avoid from degenerating, that partition edge should be chosen to divide two parts as equally as possible. Then we should merge two parts and count the valid pairs between them. It can be implemented by two sorted list that denotes the distances between u and the posterities of u and the distances between u and the posterities of v respectively. And like merge sort, use two scan line l, r in two list and maintain the property d(u, l) + d(v, r) <= k.
可見這位大牛的英文水平實在牛逼，英文說得比中文說得還清楚，贊一個。 按照這個思路，很費勁地寫出了代碼。還好，在1987上面還是勉強上榜啦！250ms那個就是我啦，哈哈。 但是在樓教主的題目1741 上面還是 TLE了。 后來找了一份能過1741的代碼，在 http://hi.baidu.com/shingray/blog/item/221362b079afc55d082302f0.html一個大牛的博客上~ 發現它的思路不是選擇一條邊來把樹分成兩份。 而是選擇一個點來把樹分成數份，然后計算經過該點的線段數目。 這樣速度就快了，大牛的代碼在1741上面只跑了170多ms。 將這份代碼放到1987上面，也能跑到260ms。 所以這種方法還是很牛逼的！ 我的垃圾代碼（POJ 1987）：
 #include <stdio.h>
#include <stdlib.h>
#define MAX_VETXS 65536*2
#define MAX_EDGES (MAX_VETXS - 1)
#if 0
#define dbp printf
#else
#define dbp( )
#endif
  struct edge_node {
 int w, i;
struct edge_node *next, *prev;
 };
struct edge_node edges[MAX_EDGES], map[MAX_VETXS];
int edges_cnt;
int N, K, ans;
int cmp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
inline int max(int a, int b)
{
return a > b ? a : b;
}
#define list_foreach(_head, _t) \
for (_t = (_head)->next; _t != _head; _t = (_t)->next)
inline void list_init(struct edge_node *t)
{
t->next = t->prev = t;
}
inline void list_add(struct edge_node *head, struct edge_node *t)
{
head->prev->next = t;
t->prev = head->prev;
head->prev = t;
t->next = head;
}
inline void list_del(struct edge_node *t)
{
t->prev->next = t->next;
t->next->prev = t->prev;
}
inline void list_rev(struct edge_node *t)
{
t->next->prev = t;
t->prev->next = t;
}
inline void edge_add(int a, int b, int w)
{
struct edge_node *t = &edges[edges_cnt++];
t->i = b;
t->w = w;
list_add(&map[a], t);
}
struct part_info {
int u, v, e, cnt_v;
};
inline void divide(int i, int *arr, int *len, int cnt, struct part_info *pi)
{
  static struct {
int i, e, depth, cnt, stat, root;
 } stk[MAX_VETXS], *sp, *top;
static int vis[MAX_VETXS], tm, best, val;
int *orig = arr;
struct edge_node *e;
best = cnt;
tm++;
top = stk + 1;
top->i = i;
top->depth = top->cnt = top->stat = top->root = 0;
vis[i] = tm;
while (top > stk) {
sp = top;
if (sp->stat) {
stk[sp->root].cnt += sp->cnt;
if (arr && sp->depth <= K)
*arr++ = sp->depth;
val = max(sp->cnt, cnt - sp->cnt);
if (val < best) {
best = val;
pi->u = stk[sp->root].i;
pi->v = sp->i;
pi->e = sp->e;
pi->cnt_v = sp->cnt;
}
top--;
continue;
}
sp->stat++;
list_foreach(&map[sp->i], e) {
if (vis[e->i] == tm)
continue;
vis[e->i] = tm;
top++;
top->i = e->i;
top->e = e - edges;
top->depth = sp->depth + e->w;
top->cnt = 1;
top->stat = 0;
top->root = sp - stk;
}
}
if (len)
*len = arr - orig;
}
void conquer(struct part_info *pi, int cnt)
{
struct part_info pl, pr;
static int arr_l[MAX_VETXS], arr_r[MAX_VETXS], len_l, len_r, l, r;
if (cnt <= 1)
return ;
list_del(&edges[pi->e]);
list_del(&edges[pi->e ^ 1]);
divide(pi->u, arr_l, &len_l, cnt - pi->cnt_v, &pl);
divide(pi->v, arr_r, &len_r, pi->cnt_v, &pr);
qsort(arr_l, len_l, sizeof(arr_l[0]), cmp);
qsort(arr_r, len_r, sizeof(arr_r[0]), cmp);
r = len_r - 1;
for (l = 0; l < len_l; l++) {
while (r >= 0 && arr_l[l] + arr_r[r] + edges[pi->e].w > K)
r--;
ans += r + 1;
}
conquer(&pl, cnt - pi->cnt_v);
conquer(&pr, pi->cnt_v);
list_rev(&edges[pi->e]);
list_rev(&edges[pi->e ^ 1]);
}
inline void solve_v2()
{
struct part_info pi;
divide(1, NULL, NULL, N, &pi);
conquer(&pi, N);
}
int main()
{
int i, a, b, w, m;
char str[16];
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &m);
edges_cnt = 0;
for (i = 1; i <= N; i++)
list_init(&map[i]);
for (i = 0; i < m; i++) {
scanf("%d%d%d%s", &a, &b, &w, str);
edge_add(a, b, w);
edge_add(b, a, w);
}
scanf("%d", &K);
ans = 0;
solve_v2();
printf("%d\n", ans);
return 0;
}
大牛的代碼（POJ 1987）：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <limits>
#include <queue>
#include <vector>
using namespace std;
const int MAX_N = 65536*2;
bool flag[MAX_N];
int k, n, ret, v[MAX_N];
queue<pair<int, int> > q;
struct edge{int v, w; edge *next; } *e[MAX_N], data[MAX_N*2-2], *it;
void insert(int u, int v, int w)
{
*it = (edge){v, w, e[u]}; e[u] = it++;
*it = (edge){u, w, e[v]}; e[v] = it++;
}
int count(int *first, int *last)
{
int ret = 0;
sort(first, last--);
while (first < last)
if (*first+*last <= k) ret += last-first++;
else --last;
return ret;
}
int best_size, center;
int centerOfGravity(int root, int pred)
{
int max_sub = 0, size = 1;
for (edge *it = e[root]; it; it = it->next)
if (it->v != pred && flag[it->v])
{
int t = centerOfGravity(it->v, root);
size += t;
if (t > max_sub) max_sub = t;
}
if (q.front().second-q.front().first-max_sub > max_sub)
max_sub = q.front().second-q.front().first-max_sub;
if (max_sub < best_size)
best_size = max_sub, center = root;
return size;
}
int dists[MAX_N], len;
void find(int root, int pred, int dist)
{
v[len] = root;
dists[len++] = dist;
int last = len;
for (edge *it = e[root]; it; it = it->next)
if (it->v != pred && flag[it->v])
{
find(it->v, root, dist+it->w);
if (pred == -1)
{
q.push(make_pair(last, len));
ret -= count(dists+last, dists+len);
last = len;
}
}
}
int main()
{
int m;
char str[16];
scanf("%d%d", &n, &m);
{
it = data;
memset(e, 0, sizeof(e[0])*n);
for (int i = n; --i; )
{
int u, v, w;
scanf("%d%d%d%s", &u, &v, &w, str);
--u; --v;
insert(u, v, w);
}
scanf("%d", &k);
ret = 0;
for (int i = 0; i < n; ++i)
v[i] = i;
for (q.push(make_pair(0, n)); !q.empty(); q.pop())
{
if (q.front().first == q.front().second-1) continue;
for (int i = q.front().first; i < q.front().second; ++i)
flag[v[i]] = true;
best_size = numeric_limits<int>::max();
centerOfGravity(v[q.front().first], -1);
len = q.front().first;
find(center, -1, 0);
ret += count(dists+q.front().first, dists+q.front().second);
for (int i = q.front().first; i < q.front().second; ++i)
flag[v[i]] = false;
}
printf("%d\n", ret);
}
}
|