|
|
這題很牛逼，是樓教主的《男人七題》的其中一道。
求：一棵樹(shù)內(nèi)最短距離小于K的點(diǎn)對(duì)數(shù)量
后來(lái)看了解題報(bào)告，原來(lái)樹(shù)也是可以分治的。
分：
選取一條邊，將一棵樹(shù)分成兩半，這兩半的節(jié)點(diǎn)數(shù)要盡量相等。
首先，統(tǒng)計(jì)個(gè)每個(gè)節(jié)點(diǎn)的下面有多少個(gè)節(jié)點(diǎn)
然后，就知道每個(gè)邊切斷之后的情況了。選擇最優(yōu)的即可。
治：
分成兩半之后，統(tǒng)計(jì)經(jīng)過(guò)該條邊的點(diǎn)對(duì)線段中，長(zhǎng)度小于K的數(shù)目。
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.
可見(jiàn)這位大牛的英文水平實(shí)在牛逼，英文說(shuō)得比中文說(shuō)得還清楚，贊一個(gè)。 按照這個(gè)思路，很費(fèi)勁地寫(xiě)出了代碼。還好，在1987上面還是勉強(qiáng)上榜啦！250ms那個(gè)就是我啦，哈哈。 但是在樓教主的題目1741 上面還是 TLE了。 后來(lái)找了一份能過(guò)1741的代碼，在 http://hi.baidu.com/shingray/blog/item/221362b079afc55d082302f0.html一個(gè)大牛的博客上~ 發(fā)現(xiàn)它的思路不是選擇一條邊來(lái)把樹(shù)分成兩份。 而是選擇一個(gè)點(diǎn)來(lái)把樹(shù)分成數(shù)份，然后計(jì)算經(jīng)過(guò)該點(diǎn)的線段數(shù)目。 這樣速度就快了，大牛的代碼在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);
}
}
|