wxwoo's blog

原题目链接

首先树剖边权转点权,把每一条边的权值下放到子节点上

在修改的时候注意最后要避开两个点的LCA,因为LCA的点权所代表的边权不在两个点的路径上

然后看见区间推平就想到了ODT

ODT比线段树短,好写,细节还比线段树少

但是不保证数据随机,ODT的时间复杂度没有保证

最后写出来跑了6s,被LCT和树剖+线段树吊打

代码如下

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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include<set>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x)
{
int ch=getchar();
T f=1;
x=0;
while(!('0'<=ch&&ch<='9'))
{
if(ch=='-')
f=-1;
ch=getchar();
}
while('0'<=ch&&ch<='9')
{
x=(x<<3)+(x<<1)+ch-48;
ch=getchar();
}
x*=f;
}
#define setit set<node>::iterator
const int N=100010;
struct node
{
int l,r;
mutable int val;
node(int L,int R=-1,int V=0):l(L),r(R),val(V){}
friend inline bool operator<(const node &a,const node &b)
{
return a.l<b.l;
}
};
set<node>s;
int n;
int u[N],v[N],head[N],nxt[N<<1],to[N<<1],val[N<<1],e;
inline void addedge(const int &u,const int &v,const int &w)
{
to[++e]=v;
val[e]=w;
nxt[e]=head[u];
head[u]=e;
}
int fa[N],son[N],dep[N],sz[N],w[N],top[N],id[N],seq[N],cnt;
char str[10];
inline setit split(const int &x)
{
setit it=s.lower_bound(node(x));
if(it!=s.end()&&it->l==x)
return it;
--it;
int l=it->l,r=it->r,val=it->val;
s.erase(it);
s.insert(node(l,x-1,val));
return s.insert(node(x,r,val)).first;
}
inline void assign(const int &l,const int &r,const int &k)
{
setit itr=split(r+1),itl=split(l);
s.erase(itl,itr);
s.insert(node(l,r,k));
}
inline void add(const int &l,const int &r,const int &k)
{
setit itr=split(r+1),itl=split(l);
for(;itl!=itr;++itl)
itl->val+=k;
}
inline int query(const int &l,const int &r)
{
int ans=0;
setit itr=split(r+1),itl=split(l);
for(;itl!=itr;++itl)
ans=max(ans,itl->val);
return ans;
}
void dfs1(const int &x,const int &f,const int &d)
{
fa[x]=f;
dep[x]=d;
sz[x]=1;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==f)
continue;
dfs1(y,x,d+1);
w[y]=val[i];
sz[x]+=sz[y];
if(sz[y]>sz[son[x]])
son[x]=y;
}
}
void dfs2(const int &x,const int &t)
{
top[x]=t;
id[x]=++cnt;
seq[cnt]=x;
if(!son[x])
return;
dfs2(son[x],t);
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==son[x]||y==fa[x])
continue;
dfs2(y,y);
}
}
inline void addchain(int x,int y,const int &k)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
add(id[top[x]],id[x],k);
x=fa[top[x]];
}
if(x==y)
return;
if(dep[x]>dep[y])
swap(x,y);
add(id[x]+1,id[y],k);
}
inline void covchain(int x,int y,const int &k)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
assign(id[top[x]],id[x],k);
x=fa[top[x]];
}
if(x==y)
return;
if(dep[x]>dep[y])
swap(x,y);
assign(id[x]+1,id[y],k);
}
inline int maxchain(int x,int y)
{
int res=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
res=max(res,query(id[top[x]],id[x]));
x=fa[top[x]];
}
if(x==y)
return res;
if(dep[x]>dep[y])
swap(x,y);
return max(res,query(id[x]+1,id[y]));
}
inline void updedge(int u,int v,const int &k)
{
if(fa[v]==u)
swap(u,v);
assign(id[u],id[u],k);
}
int main()
{
read(n);
for(int i=1;i<n;++i)
{
int w;
read(u[i]);
read(v[i]);
read(w);
addedge(u[i],v[i],w);
addedge(v[i],u[i],w);
}
dfs1(1,1,1);
dfs2(1,1);
for(int i=2;i<=n;++i)
s.insert(node(i,i,w[seq[i]]));
int l,r,k;
while(1)
{
scanf("%s",str);
if(str[1]=='t')
break;
read(l);
read(r);
if(str[1]=='a')
printf("%d\n",maxchain(l,r));
else if(str[1]=='h')
updedge(u[l],v[l],r);
else
{
read(k);
if(str[1]=='o')
covchain(l,r,k);
else
addchain(l,r,k);
}
}
return 0;
}

原题目链接

此题显然为有向图判负权环板子题

没做过请先右转模板【负环】

此题关键点:

小明和小红的生活中,有N个关键的节点。有M个事件,记为一个三元组(Si,Ti,Wi),表示从节点Si有一个事件可以转移到Ti,事件的效果就是使他们之间的距离减少Wi。

所以建边时,要把权值变为相反数

然后以1为源点进行SPFA求负环,就AC了

……吗?

原题目链接

先无视租机器,明显的最大权闭合子图

最大权闭合子图:

给定一个有向图,点有点权,选择一个子图,满足子图上如果选择了一个点就必须选择它后继的所有点。最大化点权和。

我们将机器和任务都看成一个点

如果这题没有租机器,这题的建边方式就应该是这样:

  1. 源点向订单连流量为利润的边

  2. 机器向汇点连流量为购买价格的边

  3. 每个订单向需要的机器连流量为inf的边

可以发现,源点连的边都是订单的利润,汇点连的边都是机器的成本,只有机器和订单之间的边是$inf$

对于每个订单需要的相同机器,租用的价格也不一样

所以我们考虑把$inf$换成租机器的费用

原题目链接

明显的最大权闭合子图

最大权闭合子图:

给定一个有向图,点有点权,选择一个子图,满足子图上如果选择了一个点就必须选择它后继的所有点。最大化点权和。

经典的网络流问题,具体使用最小割求解

我们将顾客和通讯站都看成一个点,然后如下建边:

  1. 源点向顾客连流量为利润的边

  2. 通讯站向汇点连流量为成本的边

  3. 每个顾客向需要的通讯站连流量为inf的边

原题目链接

树上链最值查询

做法很多,LCT,树上倍增,树剖都可以

但由于LCT常数过大,树上倍增比树剖常数大,这里使用树链剖分

边权转点权是树剖常用套路,将边权转成深度较大的点的点权,查询时注意避开两点的LCA的权值

由于不带修改,树剖后用ST表维护,时间复杂度$\mathcal{O}(n\log n)$,比用线段树维护$\mathcal{O}(n\log ^2n)$还少一个log


载入天数...载入时分秒...


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 , 总访问量为 次 。