弦图染色问题

关于弦图和弦图的各类应用,陈丹琦的论文中已经介绍的非常清楚。 弦图与区间图 接下来我将用自己的语言解释一下弦图的染色问题 先来说几个概念 子图: 图$G=(V,E),G'=(V',E'),V'\subseteq V,E'\subseteq E$,则认为G'是G的一个子图 诱导子图:图$G=(V,E) …
BZOJ2115 Xor

题目大意 给定一张n个点,m条边的无向图,边上有权。 定义一条路径的权值为这条路径上所有边权的异或和。 求一条1到n的路径,可以经过重复的边和点,使得这条路径的权值最大。输出最大的权值。 Solution 由于权值是异或和,所以把一条路径重复经过两次是没有意义的。贡献答案的,只有图中的一些简单环和一 …

在WC划水后的第一篇博客,算是庆祝戊戌年的到来(依然在划水) 题目大意 给你一个无向带权连通图,每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。 题目保证有解。 Solution 最小生成树?kruskal?prim?应该都可以。我使用了方便的kruskal。 然而有一个限制: …

题目大意 给定一张网络,询问其中的每条有向边是否可能属于某一个最小割,是否一定属于所有最小割。 Solution 题目是最小割,肯定先跑一次网络流模板…… 求出最小割后,就可以得到一个残余网络。如果对这个残余网络进行强联通缩点,可以发现s,t一定不在同一个强联通分量中。否则,s,t之间肯定还能继续增 …
BZOJ3572 [Hnoi2014]世界树

题目大意 一棵树,边权为1。次询问。 每次给出个关键点,树上的每一个点被离它最近的关键点管理,如果两个关键点和它距离相等,那么取序号小的那个关键点。 问每个关键点管理多少点。 $ n, q \leq 300000, \sum{m} \leq 300000 $ 题解 建完虚树后跑DP算出每个关键点被哪 …

题目大意 给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小。 Solution 如果我们能知道这棵树里的任意一棵子树,我们一定可以用${size}log_{size}$的复杂度(size表示子树大小)计算出这棵子树内通过根的所以符合条件的路径。具体实现枚举这个根的每棵子树,用map维护 …

题目大意 给出一个n个节点的有根树(编号为0到n-1,根节点为0)。一个点的深度定义为这个节点到根的距离+1 设dep[i]表示点i的深度,LCA(i,j)表示i与j的最近公共祖先 有q次询问,每次询问给出l r z,求$\sum_{i=l}^{r}deep[LCA(i,z)]$ 题解 做这题,首先 …

题目大意 给定一棵带边权的树,有q次询问,每次给定m个关键点,要求删掉一些边,使得根不与任何关键点连通。 题解 咳咳 只要会虚树,这就是一道裸题。 我这种蒟蒻也只会写裸题了。。。 对每次询问建一遍虚树,然后在虚树上跑DP。 代码 #include <cstdio> #include …

题目大意 你要对一些员工进行裁员,裁掉一个员工都可以获得一些收益(可能为负)。员工之间有上下级关系,要裁掉一个员工,必须要裁掉他的所有下属。问获得的最大收益是多少。 Solution 对于这种最大收益的题,我们可以考虑构造最小割模型。假设我们已经裁掉了那些收益为正的人,但不能裁了上司而不裁下属。设置 …