发表于 | 分类于 | | + s

模板及讲解

二分图相关定义

二分图：对于某无向图 ，若它的顶点可以划分为两个互不相交的子集 ，且每条边的两端点分别属于两子集 ，则称该图为二分图
（二分图）匹配：选择一个 边集 ，使得任意边 不存在重复的顶点 ，称该边集为该（二分）图的一个 匹配 。
极大匹配：对于一个匹配，若无法在原图中找到任意边加入匹配，则称该匹配为一个极大匹配。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配 。
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边 …形成的路径叫 交替路 。
增广路：对于一条路径，从一个未匹配点出发，走交替路，终止于另一个未匹配点 ，则这条交替路称为增广路

增广路的性质：
1、具有奇数条边
2、起点和终点均为未配对点
3、整条路径上奇数边均不在原匹配中，偶数边均在原匹配中

二分图的最大匹配

普通网络流做法$O(n \sqrt{m})$：
dinic虽是$O(n^2m)$的，但是做二分图被证明了复杂度为$O(n \sqrt{m})$，详情做法看最大流最小割 算法笔记

匈牙利算法做法$O(nm)$：
算法思路大致为(具体实现看相关代码)：先枚举每个左边点DFS找右边点匹配，如果当期右边点没有被匹配，就匹配；如果被匹配了，就继续DFS这个右边点匹配的左边点找另外的点匹配，如果找得到，就完成匹配；找不到，就不能够匹配了
比较”专业”的说法：
找到一未配对点$ u$，从 $u $为端点的边中任选一条尝试配对（令其另一端点为$ v$），若此时$ v$ 未配对，则配对成功，答案更新。若点$ v$ 已经被配对，就尝试从$ v $出发“扩展”该交替路，执行递归操作，尝试找到一条增广路，若成功，对该增广路取反，即回溯更新配对关系。若失败，则尝试换一条以 $u$ 为端点的边重复操作，直至$ u$ 配对成功或全部尝试过为止。
对所有剩下的未配对点进行操作，直至尝试完毕所有点，找不到增广路为止，此时找到原图最大匹配~

二分图的最小点覆盖
定义：假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。
解法：二分图最大匹配 $=$ 二分图最小点覆盖(König 定理)
因为如果该图还会有边没覆盖到，二分图的当前匹配就不是最大匹配。因为二分图匹配必须有一条边的两端都能让出位置才能匹配。
二分图的最大独立集
定义：选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。
解法：最大独立集 $=$ 所有顶点数 $-$ 最小顶点覆盖(匈牙利算法：最大独立集 $=$ 所有顶点数 $-$最小顶点覆盖$/2$，因为匈牙利算法是针对有向边的而最大独立集的边是无向边)
这个比较显然， 最小顶点覆盖把所有边的一个顶点都算上了，其他点不会再有相邻的
二分图的最大团
定义：对于一般图来说，团是一个顶点集合，且由该顶点集合诱导的子图是一个完全图，简单说，就是选出一些顶点，这些顶点两两之间都有边。最大团就是使得选出的这个顶点集合最大。对于二分图来说，我们默认为左边的所有点之间都有边，右边的所有顶点之间都有边。那么，实际上，我们是要在左边找到一个顶点子集X，在右边找到一个顶点子集Y，使得X中每个顶点和Y中每个顶点之间都有边。
解法：二分图的最大团 $=$ 补图的最大独立集
补图的定义：对于二分图中左边一点$x$和右边一点$y$，若$x$和$y$之间有边，那么在补图中没有，否则有。
因为最大独立集是两两不相邻，所以最大独立集的补图两两相邻。
DAG的最小不相交路径覆盖
定义：在一个有向图中，找出最少的路径，使得这些路径经过了所有的点，且这些路径不可以相交。不相交即任何一个顶点有且只有一条路径与之关联。
解法：把一个点$A$拆成$A_1, A_2$，如果$A->B$，那么$A_1->B_2$。然后对新图进行二分图最大匹配，答案为 原图的节点数 $-$ 新图的二分图最大匹配
因为先假设图中的点都是独立的一条路径，而二分图最大匹配的过程就是把这些路径连起来。
DAG的最小可相交路径覆盖
定义：在一个有向图中，找出最少的路径，使得这些路径经过了所有的点，这些路径可以相交。
解法：算出图的连通性$G$，把一个点$A$拆成$A_1, A_2$，如果$G(A, B) = 1$，那么$A_1->B_2​$，转化为DAG的最小不相交路径覆盖
(以上部分内容转自此处或此处)

Dilworth 定理

参见Luogu 4934

模型

行列匹配法(连边代表点思想)
有很多箭，每根箭可以杀死一行或者一列的敌人，我们要杀死所有的敌人至要用到几根箭？
解：每个敌人的坐标$(x, y)$建图，由左边$x$连向右边$y$，然后求最小顶点覆盖即可。
因为这个图中的一条边$(x, y)$相当于原来的$(x, y)$处的敌人，所以覆盖所有边即可以全部杀死。
例题: Bzoj 1059, caioj 1126

黑白染色法(匹配思想)
给出一个网格图，棋盘有些格子是不能放东西的。现在要判断在所以可以放东西的格子上是否能用$1 \times 2$的小方块填满。
解：将图黑白染色，即相邻的格子颜色不同(黑白相间)。本题就是相当于将白格和黑格进行匹配，连边二分图，然后求出最大匹配即可。但是最大匹配后可能还会有$1 \times 1$的小方块不在匹配中，要验证答案。
例题: poj 2446

反建法(逆向思维)
也就是依据题目要求的答案反着建图。

拆点法
见最小路径覆盖。

一行变多行，一列变多列法
例题: Hdu 1045

常见题型

1、求二分图的最大匹配
Q: 给定一个二分图，求它的最大匹配
解: 见解析
例题:Bzoj 1191
2、求二分图最小点覆盖
Q: 给定一个二分图，求它的最小点覆盖
解: 见解析
例题:caioj 1125
3、求二分图的最大独立集
Q: 给定一个二分图，求它的最大独立集
解: 见解析
例题:
4、二分图的最大团
Q: 给定一个二分图，求它的最大团
解: 见解析
例题:
5、DAG的最小不相交路径覆盖(拆点)
Q: 给定一个DAG图，求它最小不相交路径覆盖
解: 见解析
例题:Bzoj 2150
6、DAG的最小可相交路径覆盖(拆点)
Q: 给定一个DAG图，求它最小可相交路径覆盖
解: 见解析
例题:
7、行列匹配法(模型, 以上题型为基础题型)
Q: 有很多箭，每根箭可以杀死一行或者一列的敌人，我们要杀死所有的敌人至要用到几根箭？
解: 见解析
例题: Bzoj 1059, caioj 1126
7、黑白染色法
Q: 见解析
解: 见解析
例题: poj 2446
8、反建法
Q: 见解析
解: 见解析
例题:
9、拆点法
Q: 见解析
解: 见解析
例题: Bzoj 2150
10、一行变多行，一列变多列法
Q: 见解析
解: 见解析
例题: Hdu 1045

阅读全文 »

发表于 | 分类于 | | + s

Bzoj 1090
这题和Bzoj 1068差不多，但是简单一些，1068的一个M对应很多R，而1090括号一一对应，使得这题的转移变得非常简单了。
设$f(i,j)$为$[i,j]$折叠后的长度(包括括号的长度)
考虑枚举中间点，$f(i,j)=min(f(i,k)+f(k+1,j))$
而只压缩前后的情况，由于括号一一对应，所以这些情况都在上面的情况之中了，不同于1068
而整个区间压缩，$f(i,j)=min(f(i,i+k-1)+cal(len/k)$，其中$len=j-i+1$.当且仅当$[i,j]$为长为$k$的子串循环而来，$cal(k)$用来计算括号的长度
边界值：$f(i,i)=1$，所有$f(i,j)$初始化为$j-i+1$
然后就可以DP了，同样记忆化搜索好写一些，用记忆化，不用考虑枚举顺序

阅读全文 »

发表于 | 分类于 | | + s

模板及讲解

大部分文字来自 背包九讲。

完全背包问题

有$ N $种物品和一个容量为$ V $的背包，每种物品都有无限件可用。放入第$ i $种物品的费用是$ C_i $，价值是$ W_i $。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。

基本方程

令$ F [i, v] $表示前$ i $种物品恰放入一个容量为$ v $的背包的最大权值。
$F [i, v] = max(F [i − 1, v − kC_i] + kW_i |0 ≤ kC_i ≤ v)$

转化 01 背包

把第$ i $种物品拆成费用为$ C_i2^k$、价值为$ W_i2^k $的若干件物品$(C_i2^k ≤ V)$
这是二进制的思想。因为，不管最优策略选几件第$ i $种物品，其件数写成二进制后，总可以表示成若干个$ 2^k $件物品的和。这样一来就把每种物品拆成$ O(log ⌊V /Ci⌋) $件物品
然后可以运用这些物品做 01 背包。

O(VN) 算法

$F [i, v] = max(F [i − 1, v], F [i, v − C_i] + W_i)$

多重背包问题

有$N$种物品和一个容量为$V $的背包。第$i$种物品最多有$M_i$件可用，每件耗费的空间是$C_i$，价值是$W_i$。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

基本方程

令$F [i, v]​$表示前$i​$种物品恰放入一个容量为$v​$的背包的最大价值
$F [i, v] = max(F [i − 1, v − kC_i] + kW_i | 0 ≤ k ≤ M_i)$

转化 01 背包

把每个物品拆成带权$2^0,2^1,2^2,……,2^{k-1},M_i-2^k+1$的物品，然后做 01 背包即可。

O(VN) 算法

单调队列优化

混合三种背包问题

for (int i = 1; i <= n; i++) {
  if (i 是 01 背包) 做 01 背包; 
  else if (i 是 完全背包) 做完全背包;
  else if (i 是 多重背包) 做多重背包;
}

分组背包

基本方程

解决什么问题

每组之间独立，每组只选一个。
那么如果我们做 01 背包时发现有物品不止一个值，并且这个值可以全部暴力算出来，那么我们可以暴力算出来一个物品所有取值，然后分组地取。

例题：CF 946D

意思就是逃课。怎样逃课才能使得最后上完课的时间减去最开始的上课的时间最短。这里是按$0$和$1$来代表有没有课，$1$代表有课，可以逃。但是最多只能逃$k$节课。

发现可以 DP，但是真心不会转移怎么办？我们看每天，逃不同数量的课有不同的收益。所以我们把一天看成一组，预处理逃不同数量的课有不同的收益，做一个分组背包即可。

发表于 | 分类于 | | + s

Bzoj 1079
这种题目还是往DP和排列组合想。
直接存颜色用了多少是$5^{15}$的，会炸。我们选择把剩余可涂次数相等的分为一类，考虑因为只要剩余可涂次数相等，那么其实这些颜色并没有什么区别，因为我们涂颜色的时候只需要考虑涂的这种颜色剩余次数即可，并不需要考虑具体是什么颜色（先不考虑相邻颜色不能相等的限制）。
那么令$f(a1, a2, a3, a4, a5)$表示剩余可涂一次的颜色种类数为$a1$，涂二次颜色种类数为$a2$…这样的情况的方案数。
　　显然如果我们当前这次选的是剩余次数为$x$次的颜色，那么剩余次数为$x$次的颜色有多少种，就有多少种情况可以转移过来，只需要乘以数量就可以了（相当于每个格都可以填这些颜色）。
　　但是我们还没考虑相邻不能相等的情况，那么我们必须要少算一次，比如说如果上次填的是颜色剩余次数为2的，意味着颜色中剩余次数为1的多了一个，那么这一次并不能再选这种颜色，这次可以选填1的就要少1。
以上转自此处

阅读全文 »

发表于 | 分类于 | | + s

模板及讲解

树上背包

问题：给$n$个物品，物品之间有依赖关系，每个物品有重量$w_i$和价值$v_i$，求取物品的最大价值。
解：给定的是一个森林，我们要把森林的根节点全部连到$0$号节点，然后树形DP，设$dp(u, i)$为以$u$为根的子树必选$u$选$i$重量的物品时的最大价值，那么$dp(u, i) = dp(u, i-j) + dp(v, j)$，之后因为要必选$u$，所以大于$w_u$的$i$的$dp(u, i) = dp(u, i-w_u) + v_u$，小于$w_u$的$i$的$dp(u,i) = 0$.

树的重心(质心)

问题：求出一棵无根树的某个点，使得这个点当做根以后最大子树的节点数最小
解：求出每棵树的子树节点数$siz_u$，每个节点作为根时深度$blc=max(siz_v, n-siz_u)$，$v \in son(u)$,然后答案就是$min(blc)$

性质：
1把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。(用于合并信息的性质)
2把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离
3去掉任意一个重心后，生成的各个块的节点数的最大值一定小于等于原树的节点数除以2。
4以一棵树的重心为根的子树的节点个数，一定大于等于该树节点总数的一半。
5在一棵树的所有子树中，找到某一子树，使得其节点数恰好大于等于原树节点总数一半，那么该子树的根一定是一个重心。(如果该节点不是重心，也就是把它去掉后产生的连通块中至少有一个节点个数大于原树节点个数的一半。)

45互逆

树的直径(最长路径, 最远点对)

问题：求出树上最长的一条链
解：两次 BFS。第一次随便找一个点 BFS 找到离这个点最远的那个点$u$，用$u$继续 BFS 找离这个点最远的那个点$v$，则链$uv$为树的直径

性质(直径常用反证矛盾法)：
1距离树上任意节点最远的点 一定是树点直径的两个端点之一
2以树的直径中点上的一点为根，将这颗无根树转化为有根树的话，这样做会使树的深度最小，且为树的直径的一半（向上取整）(因为如果有一个叶子节点比直径更深的话，那么就可以构成一个更长的直径，与假设矛盾。)
3所有直径的中心相同，这个中心可以是一个顶点，也可以在一条边上。所有点到他的最远点都要通过这个中心
4树的直径的端点必然是他的子树直径的端点(用于合并信息的性质)
5有两棵树，如果把它们随意连一条边，会变成一棵树，新树的直径的端点一定是之前两棵树的直径的共4个端点的两个

树的最大独立集

问题：
解：

环套树DP

基本思路：
1、有可能是断环边后树处理：Bzoj 1040，NOIP2018Day2T1
2、有可能是找到唯一环后将这个环作为一个广义根，然后再结合环一起计算：Bzoj 1791

问题1：给定$n$个点，$n$条边，保证任意两点间至少存在一条路径。其中每个点均有其权值$v_i$，问如何选择点，使得在保证任意直接相连的两点不会同时被选中的情况下，被选中的点的权值和最大？
解：对于一棵$n$个节点的树，必然有$n-1$条边，对于一个$n$个点$n$条边构成环的图，我们可以断开这条使得树变成环的边，然后用树形DP设$dp(u,0)$为以$u$为根的子树的最大权和并且不能选$u$, $dp(u,0)$为以$u$为根的子树的最大权和并且必选$u$。然后就对这条边的两个顶点进行两次树形DP，答案就是$max(dp(u, 0), dp(v, 0))$。(第一个是第一次DP的结果，第二个是第二次DP的结果)。为什么要进行两次DP呢，因为如果我们只DP$u$，那么选$u$的方案就不能得到(如果取01最大值，那样会有可能$u, v$同选，不满足题意)，就会漏解。

注意以下数据：
Markdown

常见题型

1、常规树形DP
Q: 在树上的DP。
解: 通常用dfs完成，从叶子推到根。
例题: Bzoj 1369
2、树上背包
Q: 见讲解
解: 见讲解
例题: Bzoj 2427
3、求树的重心
Q: 见讲解
解: 见讲解
例题: Poj 1655
4、求树的直径
Q: 见讲解
解: 见讲解
例题:
5、求树的最大独立集
Q: 见讲解
解: 见讲解
例题:
6、环套树DP(标志：$n$个点$n$条边)
Q: 见讲解
解: 见讲解
例题: Bzoj 1040
7、树上选点覆盖
Q: Bzoj 1596
解:$f(u, 0)$为不在$u$建基站，$u$与$u$的子树都有信号。$f(u, 1)$为在$u$建基站，$u$与$u$的子树都有信号。$f(u, 2)$为不在$u$建基站，$u$没有信号，$u$的子树都有信号。
例题: Bzoj 1596

发表于 | 分类于 | | + s

BZOJ 1007
其实是求一个半凸包(从左到右依次观察每条边和每个顶点，发现其斜率不断增大，顶点的横坐标也不断增大)，我们把直线按斜率$k$从小到大排，$k$一样$b$从大到小排。只处理$b$最大的那条直线，因为这样和之前的直线交点尽可能右。

我们维护一个单调栈$S$，如果当前直线i能完全覆盖栈顶直线$S_{top}$，则$i$与$S_{top}$的交点一定在$S_{top}$与$S_{top-1}$的交点左边或者重合。若在它左边或者重合，则弹出栈顶，直到交点在右边后，扔进栈里。最后栈中元素就是答案。

程序实现时，不直接放两个直线不用复杂判斜率相同！

阅读全文 »