分类: [图论]

弦图染色问题

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

BZOJ2115 Xor

题目大意 给定一张n个点,m条边的无向图,边上有权。 定义一条路径的权值为这条路径上所有边权的异或和。 求一条1到n的路径,可以经过重复的边和点,使得这条路径的权值最大。输出最大的权值。 Solution 由于权值是异或和,所以把一条路径重复经过两次是没有意义的。贡献答案的,只有图中的一些简单环和一条1到n的路径。 我们可以事先选出一条1到n的路径(任意),记为“主路径”。假设我们沿着这条路径由1走到n,并得到了这条路径的权值,记为ans。 再将所有环的异或和求出来。最后的答案就是在选取一些环的异或和和ans的异或和的最 ......

BZOJ2654 tree

在WC划水后的第一篇博客,算是庆祝戊戌年的到来(依然在划水) 题目大意 给你一个无向带权连通图,每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。 题目保证有解。 Solution 最小生成树?kruskal?prim?应该都可以。我使用了方便的kruskal。 然而有一个限制:恰好使用need条白色边。 考虑给让白色边的边权都加上一个正数,这样就可以在最小生成树中选择更少的白色边;加上一个负数同理。于是可以枚举这个值,给所有白色边都加上这个值后跑最小生成树,再看生成树的白色边是不是need条。而这个值显然是可以二 ......

BZOJ1797 mincut最小割

题目大意 给定一张网络,询问其中的每条有向边是否可能属于某一个最小割,是否一定属于所有最小割。 Solution 题目是最小割,肯定先跑一次网络流模板…… 求出最小割后,就可以得到一个残余网络。如果对这个残余网络进行强联通缩点,可以发现s,t一定不在同一个强联通分量中。否则,s,t之间肯定还能继续增流,求出的肯定不是最大流。 如果原图中一条边是u->v的,且任意一点u缩点后属于belong[u]的强联通分量中。 如果这条边没有满流,显然它不可能属于某一个最小割。 如果belong[u]!=belong[v],则边u->v可以属于某一个最小割。 ......

BZOJ3572 [Hnoi2014]世界树

题目大意 一棵树,边权为1。次询问。 每次给出个关键点,树上的每一个点被离它最近的关键点管理,如果两个关键点和它距离相等,那么取序号小的那个关键点。 问每个关键点管理多少点。 $ n, q \leq 300000, \sum{m} \leq 300000 $ 题解 建完虚树后跑DP算出每个关键点被哪个点管理以及距离。 然后对虚树中的每条边计算答案,以及计算不再虚树中的点的答案。 代码 C++ #include <cstdio> #include <cstring> #include <algorithm> const int INF = 1e9; int n, m; int x[8000 ......

BZOJ2599 Race(点分治)

题目大意 给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小。 Solution 如果我们能知道这棵树里的任意一棵子树,我们一定可以用${size}log_{size}$的复杂度(size表示子树大小)计算出这棵子树内通过根的所以符合条件的路径。具体实现枚举这个根的每棵子树,用map维护一下就好了。(map大法好)。 用分治的思想,计算完整棵树后,把它分成若干棵相同结构的子树,再计算答案。所以只要能找到一个合适的分治点,就可以得到较好的复杂度。 具体实现时,可以找到整棵树的重心,把它作为根,并将它作为分治点继续分治。 因为 ......

BZOJ3626 LCA

题目大意 给出一个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)]$ 题解 做这题,首先要发现一个事实:两个点的LCA的深度就是两个点分别到根的链的公共点 所以,对于一次询问,可以将[l,r]区间内的点到根的链的每一个的权值+1,答案即为z到根的链上的点的权值和 这个是可以用树链剖分维护的 对于多次询问,我们将一个询问变成[1,l-1]和[1,r]两个询问,将询问排序,一边更新 ......

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 ......

POJ2987 Firing

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