我是靠谱客的博主 辛勤烤鸡,这篇文章主要介绍BZOJ2599 [IOI2011]Race 【点分治】,现在分享给大家,希望可以做个参考。

题目

给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000

输入格式

第一行 两个整数 n, k
第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始)

输出格式

一个整数 表示最小边数量 如果不存在这样的路径 输出-1

输入样例

4 3

0 1 1

1 2 2

1 3 4

输出样例

2

提示

2018.1.3新加数据一组,未重测

题解

比较常规的点分治,然而我还是因为不熟练写漏一个判定T得停不下来QAQ

每次找重心,遍历子树维护H数组H[i]表示离根i距离经过的最少边,每次遍历完一个子树,先查询一遍H数组更新答案,再更新H数组,保证不会出现在同一个子树中的情况

遍历完之后,再遍历一遍,把H数组还原【别memset,会T,因为每一层的节点数是不同的,才使得复杂度降低为O(nlogn),而使用memset使得每一层操作都达到n】

之后往下找重心递归
搞完啦~~

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long int #define REP(i,n) for (int i = 1; i <= (n); i++) #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt) using namespace std; const int maxn = 200005,maxm = 1000005,INF = 1000000000; inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57) {out = (out << 3) + (out << 1) + c - '0'; c = getchar();} return out * flag; } int N,K,h[maxn],ne = 2; struct EDGE{int to,nxt,w;}ed[2 * maxn]; inline void build(int u,int v,int w){ ed[ne] = (EDGE){v,h[u],w}; h[u] = ne++; ed[ne] = (EDGE){u,h[v],w}; h[v] = ne++; } int F[maxn],rt,Siz[maxn],vis[maxn],sum; void getRT(int u,int fa){ Siz[u] = 1; F[u] = 0; Redge(u) if (!vis[to = ed[k].to] && to != fa){ getRT(to,u); Siz[u] += Siz[to]; F[u] = max(F[u],Siz[to]); } F[u] = max(F[u],sum - Siz[u]); if (F[u] < F[rt]) rt = u; } int Dis[maxn],Len[maxn],di = 0,Hd[maxm],dis[maxn],dep[maxn],ansL = INF; void cal(int u,int fa){ if (dis[u] > K) return; Dis[++di] = dis[u]; Len[di] = dep[u]; Redge(u) if (!vis[to = ed[k].to] && to != fa){ dis[to] = dis[u] + ed[k].w; dep[to] = dep[u] + 1; cal(to,u); } } void solve(int u){ vis[u] = true; Hd[0] = 0; Redge(u) if (!vis[to = ed[k].to]){ di = 0; dis[to] = ed[k].w; dep[to] = 1; cal(to,u); REP(i,di) if (Hd[K - Dis[i]] + Len[i] < ansL) ansL = Hd[K - Dis[i]] + Len[i]; REP(i,di) if (Hd[Dis[i]] > Len[i]) Hd[Dis[i]] = Len[i]; } Redge(u) if (!vis[to = ed[k].to]){ di = 0; dis[to] = ed[k].w; dep[to] = 1; cal(to,u); REP(i,di) Hd[Dis[i]] = INF; } Hd[0] = INF; Redge(u) if (!vis[to = ed[k].to]){ sum = Siz[to]; F[rt = 0] = INF; getRT(to,u); solve(rt); } } int main(){ //freopen("in.txt","r",stdin); //freopen("out1.txt","w",stdout); N = read(); K = read(); int u,v,w; for (int i = 0; i < maxm; i++) Hd[i] = INF; REP(i,N - 1) u = read() + 1,v = read() + 1,w = read(),build(u,v,w); F[rt = 0] = INF; sum = N; getRT(1,0); solve(rt); if (ansL == INF) printf("-1n"); else printf("%dn",ansL); return 0; }

转载于:https://www.cnblogs.com/Mychael/p/8282701.html

最后

以上就是辛勤烤鸡最近收集整理的关于BZOJ2599 [IOI2011]Race 【点分治】的全部内容,更多相关BZOJ2599内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(92)

评论列表共有 0 条评论

立即
投稿
返回
顶部