BZOJ2286 消耗战

题目大意 给定一棵带边权的树,有q次询问,每次给定m个关键点,要求删掉一些边,使得根不与任何关键点连通。 题解 咳咳 只要会虚树,这就是一道裸题。 我这种蒟蒻也只会写裸题了。。。 对每次询问建一遍虚树,然后在虚树上跑DP。 代码 C++ #include <cstdio> #include <algorithm> #include <cstring> const long long INF = 1e18; int edgenum; int vet[600000], val[600000], nextx[600000], head[300000]; int fa[300000][22]; long long f[300000]; int cnt; int ......

BZOJ3669 魔法森林

题目大意 给出一幅无向图,每个点上有两种权值A,B。 求一条1到n的路径,使路径上A的最大值+B的最大值最小。 Solution 如果要使一条路径上一种权值的最大值最小,这条路径一定在这种权值的最小生成树上。但A的最小生成树和B的最小生成树不同,所以不能直接求最小生成树。 而如果我们从小到大枚举一种权值,就可以依次加边,并知道这种权值的最大值。然后我们就只要维护另一种权值的最小生成树就可以了。 当加入了边u,v后,若原来u,v间没有路径,那么就直接连起来。u,v间原来就有路径时,由于维护了一棵树,所以路径唯一,只要看这 ......

BZOJ4521手机号码

题目大意 不包含4或8,且至少包含3个连续数字的数为合法的手机号码。问l,r区间内合法的手机号码有几个? Solution 这题是很显然的数位DP。当然,如果直接套dp方程可能会显得麻烦,所以还是用记忆化搜索。思路直接描述有点困难,所以直接看代码和注释。 代码 #include&lt;cstdio&gt;; #include&lt;algorithm&gt;; #include&lt;cstring&gt;; using namespace std; long long l,r; long long num[20][10][10][2][2][2]; int a[20]; long long dfs(int len,int p1,int ......

BZOJ2733 永无乡(线段树合并)

题目大意 给你一些点,每个点有它的点权(各不相同),一些点之间本来就有边。要维护两种操作: B u v,连接u,v两点。 Q u k,询问u所在联通块中第k小的点。 Solution 要合并两个联通块,并询问一个联通块中第k小的点,本来可以用平衡树做。用启发式合并,可以做到两个log。 我们也可以用权值线段树做。在线段树上二分的话,也可以让询问做到log。但怎么合并两棵权值线段树呢? 由于线段树的形态都是唯一的。如果要将子树x合并到子树y上去的话,只要这样就可以了: void merge(int x,int &amp ......

51nod1648 洞(Link Cut Tree)

题目传送门:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1648 将I号点和min(n+1,a[I]+I)连边,这显然是一棵以n+1号点为根的树。于是修改a[I]就相当于修改I的父亲,可以用Link Cut Tree维护。求最后一个离洞前的编号,只要给每一个点一个权值,其中1~n号点的权值为I,n+1号点的权值为0。跳跃次数就计算也类似,给每一个点一个为1 的权,然后求和。 Code: #include&lt;stdio.h&gt; #include&lt;algorithm&gt; using namespace std; int ch[300000][2],fa[30 ......

POJ2987 Firing

题目大意 你要对一些员工进行裁员,裁掉一个员工都可以获得一些收益(可能为负)。员工之间有上下级关系,要裁掉一个员工,必须要裁掉他的所有下属。问获得的最大收益是多少。 Solution 对于这种最大收益的题,我们可以考虑构造最小割模型。假设我们已经裁掉了那些收益为正的人,但不能裁了上司而不裁下属。设置超级源,将它与所以收益为正的点连边,流量为w[i],表示裁掉了这个人,并将初始答案加上w[i],若割掉这条边,就表示不拿这个人的收益了。再将所有收益为负的点向一个超级汇连边,表示不裁这个人,流量为-w[i],若割掉这 ......