「bsoj5088」花花的聚会 - 树形动规+树链剖分/倍增 | Bill Yang's Blog

「bsoj5088」花花的聚会 - 树形动规+树链剖分/倍增

题目大意

花花住在H国。H国有$n$个城市,其中$1$号城市为其首都。城市间有$n-1$条单向道路。从任意一个城市出发,都可以沿着这些单向道路一路走到首都。事实上,从任何一个城市走到首都的路径是唯一的。
过路并不是免费的。想要通过某一条道路,你必须使用一次过路券。$H$国一共有$m$种过路券,每张过路券以三个整数表示:$v\,k\,w$:你可以在城市$v$以价格$w$买到一张过路券。这张券可以使用$k$次。这意味着,拿着这张券通过了$k$条道路之后,这张券就不能再使用了。
请注意你同一时间最多只能拥有最多一张过路券。但你可以随时撕掉手中已有的过路券,并且在所在的城市再买一张。
花花家在首都。他有$q$位朋友,他希望把这些朋友们都邀请到他家做客。所以他想要知道每位朋友要花多少路费。他的朋友们都很聪明,永远都会选择一条花费最少的方式到达首都。
花花需要准备晚餐去了,所以他没有时间亲自计算出朋友们将要花费的路费。你可以帮帮他么?


题目分析

不难想到树形动规的思路:
设$f[u]$表示从结点$u$到达根结点$1$所需要花费的路费。

我们可以将满足条件的票穿在链表中挂在树上的每一个结点上。
在每一个结点即可枚举其含有的票数,于是只需要满足深度的要求即可。
问题转化为在指定深度差中间寻找一个$f[]$最小的值出来,且动态修改$f[]$。

很显然这可以用树链剖分来维护,于是我就打了一个树链剖分(约4KB)。

考试后明白了可以使用动态倍增来实现修改操作,因为对$f[]$的修改仅影响其后代结点,因此我们可以再用$O(\log n)$在每一个结点处预处理$ST$表,然后再询问。

这样时间复杂度均摊是$O(n\log 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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int min(const int x,const int y) {
if(x<y)return x;
else return y;
}
const int maxn=100005;
struct Tree {
int left,right,min;
Tree(int l=0,int r=0,int m=0x7fffffff/2):left(l),right(r),min(m) {}
};
struct Segment_Tree {
Tree tree[maxn*4];
#define ls index<<1
#define rs index<<1|1
void build(int index,int Left,int Right) {
tree[index]=Tree(Left,Right);
if(Left==Right)return;
int mid=(Left+Right)>>1;
build(ls,Left,mid);
build(rs,mid+1,Right);
}
void push_up(int index) {
tree[index].min=min(tree[ls].min,tree[rs].min);
}
void modify(int index,int target,int v) {
if(target>tree[index].right||target<tree[index].left)return;
if(tree[index].left==tree[index].right) {
tree[index].min=v;
return;
}
modify(ls,target,v);
modify(rs,target,v);
push_up(index);
}
int query(int index,int Left,int Right) {
if(Left>tree[index].right||Right<tree[index].left)return 0x7fffffff/2;
if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index].min;
return min(query(ls,Left,Right),query(rs,Left,Right));
}
} st;
int Depth[maxn],father[maxn],Size[maxn],Son[maxn],Top[maxn],M[maxn],n,f[maxn],cnt=0;
vector<int>edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Dfs1(int Now,int fa,int depth) {
Depth[Now]=depth;
father[Now]=fa;
Size[Now]=1;
for(int Next:edges[Now]) {
if(Next==fa)continue;
Dfs1(Next,Now,depth+1);
Size[Now]+=Size[Next];
if(Size[Next]>Size[Son[Now]])Son[Now]=Next;
}
}
void Dfs2(int Now,int top) {
Top[Now]=top;
M[Now]=++cnt;
if(Son[Now])Dfs2(Son[Now],top);
for(int Next:edges[Now]) {
if(Next==father[Now]||Next==Son[Now])continue;
Dfs2(Next,Next);
}
}
void build() {
Dfs1(1,0,1);
Dfs2(1,1);
st.build(1,1,n);
}
int query(int Now,int Limit) {
int top=Top[Now],ans=0x7fffffff/2;
while(Now&&Depth[Now]-Depth[top]<=Limit) {
ans=min(ans,st.query(1,M[top],M[Now]));
Limit-=Depth[Now]-Depth[top]+1;
Now=father[Top[Now]];
top=Top[Now];
}
ans=min(ans,st.query(1,max(1,M[Now]-Limit),M[Now]));
return ans;
}
struct Ticket {
int k,v;
};
vector<Ticket>a[maxn];
void TreeDp(int Now) {
if(Now==1)f[Now]=0;
else {
f[Now]=0x7fffffff/2;
for(auto& t:a[Now])f[Now]=min(f[Now],query(Now,t.k)+t.v);
}
st.modify(1,M[Now],f[Now]);
for(int Next:edges[Now]) {
if(Next==father[Now])continue;
TreeDp(Next);
}
}
int m,q;
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
for(int i=1; i<=m; i++) {
int x=Get_Int(),k=Get_Int(),v=Get_Int();
a[x].push_back((Ticket) {
k,v
});
}
build();
TreeDp(1);
q=Get_Int();
for(int i=1; i<=q; i++) {
int x=Get_Int();
printf("%d\n",f[x]);
}
return 0;
}

xyj敲的倍增

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=100005;
const int INF=0x7fffffff/2;
int n,m,cnt,h[MAXN],f[MAXN][21],Min[MAXN][21],dep[MAXN],g[MAXN];
struct point{int to,next;}q[MAXN*2];
struct PP{int v,k;};
void AddEdge(int x,int y){cnt++;q[cnt].to=y;q[cnt].next=h[x];h[x]=cnt;}
vector<PP> Q[MAXN];
void Add(int x)
{
int i,j;
for(i=1;(1<<i)<=n;i++)
if(f[x][i-1]!=-1)
{
f[x][i]=f[f[x][i-1]][i-1];
Min[x][i]=min(Min[x][i-1],Min[f[x][i-1]][i-1]);
}
}
int Ask(int x,int k)
{
int i,minn=INF,now=x;
for(i=int(log2(dep[x]))+1;i>=0;i--)
{
if(f[now][i]!=-1&&dep[x]-dep[f[now][i]]<=k)
{
minn=min(minn,Min[now][i]);
now=f[now][i];
}
}
return minn;
}
void DFS(int x,int fa)
{
int i,y,minn=INF;
Add(x);
for(i=0;i<Q[x].size();i++)
{
PP t=Q[x][i];
minn=min(minn,Ask(x,t.k)+t.v);
}
if(x!=1) g[x]=minn;
else g[x]=0;
for(i=h[x];i;i=q[i].next)
{
y=q[i].to;
if(y==fa) continue;
f[y][0]=x;dep[y]=dep[x]+1;Min[y][0]=g[x];
DFS(y,x);
}
}
int main()
{
//freopen("party.in","r",stdin);
//freopen("party.out","w",stdout);
int i,j,k;
scanf("%d%d",&n,&m);
for(i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
AddEdge(x,y);AddEdge(y,x);
}
for(i=1;i<=m;i++)
{
int v,K,w;
scanf("%d%d%d",&v,&K,&w);
PP t=(PP){w,K};
Q[v].push_back(t);
}
dep[1]=1;
memset(f,-1,sizeof(f));
for(i=1;i<=n;i++)
for(j=0;j<=20;j++)
Min[i][j]=INF;

DFS(1,0);

int T;
scanf("%d",&T);
while(T--)
{
int x;
scanf("%d",&x);
printf("%d\n",g[x]);
}

return 0;
}

姥爷们赏瓶冰阔落吧~
0%