P4334 [COI2007] Policija 题意 一个无重边的无向图，每次询问删掉一条边或删掉一个点后两个点是否联通。 思路 连通性问题，我们可以考虑使用广义圆方树解决。 对于删掉一个点的情况： 我们先跑 tarjan 建出圆方树。如何判断两点在删去一个点后在树上的连通性？当且仅当被删去的点在两点间的路径上。根据圆方树的性质，如果被删点在一个点双连通分量中，它是符...

P5296 [北京省选集训2019]生成树计数 题意 求一个带权无向图所有生成树边权和的 \(k\) 次方的和。 思路 首先有一个结论：\(a^i\) 的 EGF 卷 \(b^i\) 的 EGF 等于 \((a+b)^i\) 的 EGF。即： \[ F(a)=\sum_{i=0}\frac{a^ix^i}{i!}\\ F(a+b)=F(a)*F(b) \] 证明如下： \[...

P5311 [Ynoi2011] 成都七中 题意 给你一棵 \(n\) 个节点的树，每个节点有一种颜色，有 \(m\) 次查询操作。 查询操作给定参数 \(l\ r\ x\)，需输出： 将树中编号在 \([l,r]\) 内的所有节点保留，\(x\) 所在连通块中颜色种类数。 每次查询操作独立。 思路 考虑点分树的思想。假设我们已经建出点分树，对于每一个分治中心，我们应该...

P5471- K-D tree优化建图-弹跳 优化建图是一种思想。 题意 有\(n\)个城市分布在小鸟岛上，有\(m\)个弹弓分布在这些城市里。因为弹弓体积大，固定麻烦，所以每个弹弓只能把小鸟弹飞到一块固定的矩形范围内的城市，同时小鸟会在空中滞留\(t_i\)的时间。闪电黄的家在1号城市，追求速度的它想知道，若只使用弹弓出行，它从家到其他所有城市的最短时间花费是多少。 抱歉魔...

P6295 有标号 DAG 计数 题意 求 \(n\) 个点有标号弱联通 DAG 数量。 推导 设 \(f_i\) 表示 \(i\) 个点有标号 DAG 数量（不保证弱联通），有： \[ f(i)=\sum_{j=1}^i\binom ij(-1)^{j-1}f(i-j)2^{j(i-j)} \] 意义为选至少 \(j\) 个度数为零的点，向剩下的 \(i-j\) 个点随...

因为是单向边，牛儿来回的路径长度并不相同，所以需要用两次 dijkstra，一次正向从 \(x\) 开始 dijkstra，再将边全部反向存再来一次。 因为是板子题比较良心 \(n\) 比较小，我们就可以用矩阵来存储啦。如果 \(n\) 比较大的话，我的想法是再造一个图，同时反向存边。内存可能占用比较大但是想起来简单。 代码很短。 12345678910111213141516...

Description 墨墨突然对等式很感兴趣，他正在研究 \(a_1x_1+a_2x_2+...+a_nx_n=B\) 存在非负整数解的条件，他要求你编写一个程序，给定 \(N\)、\(\{a_n\}\)、以及 \(B\) 的取值范围，求出有多少 \(B\) 可以使等式存在非负整数解。 Input 输入的第一行包含 3 个正整数，分别表示 \(N\)、\(B_{Min}\)、\(B...

前言 前几天考试了发现这个东西完全不会欸……学了又忘真是讨厌至极 QAQ 所以又在网上找着看了看写一篇博客备忘。 学习笔记真的很有用！ 分层图 这个很容易理解，来源就是在一些最短路的问题上题目又加了比如说主角可以用传送宝石进行折跃之类的问题（针对），即可以选择k条边把这些边的边权变为零。 怎么样解决呢？可以在原图的基础上多复制k个相同的图，并用k条边把图之间的边用0边权边相连。就...

无用的文字 又是一篇笔记，因为不做题的话太容易忘了啊啊啊QAQ看到一个题目知道用什么算法做但就是想不出来的感觉太难受了…… 二分图最大匹配 二分图 二分图是指可以被分为两个不相交点子集的图，其中相同点集内无连边。 匈牙利算法 匈牙利算法是用来寻找最大匹配的一个算法。 交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边……形成的路径叫交替路。 增广路：从一个未匹...

并查集 并查集是一种树型数据结构，用于处理一些动态集合的合并及查询问题。 并查集的基本操作有： 合并：将两个集合合并为一个集合。 查询：判断两个元素是否属于同一个集合。 并查集的应用场景有： 动态连通性：判断两个点是否连通。 最小生成树：计算最小生成树。 路径压缩：减少树的高度。 并查集优化 并查集有两种启发式优化。第一种是路径压缩，即将每个节点的父节点压...