zcmimi's blog

arrow_back图论共19篇文章

avatar
zcmimi
2020-09-28 14:07:23

prufer序列

这是一种将带标号的树用一个唯一的整数序列表示的方法.

很多与度数有关的树上计数问题,都可以用它以及它的性质来解决

kruskal重构树

我们回想一下kruskal生成最小生成树的过程:

先将边按边权从小到大排序,然后依次加入

如果x,y已经联通,则跳过这条边

否则连接x,y

kruskal重构树是在kruskal生成最小生成树的,

连接x,y时,将边权变成一个新的节点$

avatar
zcmimi
2019-01-30

建树

tarjan求出双连通分量后把其中的点连向新建的节点

建成的新图(树)即为圆方树

**性质:可

avatar
zcmimi
2018-10-27

差分约束的具体概念:

如果一个系统由n个变量和m个约束条件组成,形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统。

例子:

假设有3个数a,b,c 我们知道:

a-b>=2
b-c>=3
a-c>=3

那么:a与c的差

avatar
zc
2020-10-20 16:36:54

查看原题

点击跳转

建图比较麻烦的最短路问题

将每个城市考虑为4个机场

每个机场两两之间互相连边,若同一个城市,走高速,否则走航线

需要注意的是找出根据三个机场找出第四个机场时的分类讨论

avatar
zc
2020-10-12 16:35:55

查看原题

点击跳转

矩阵加速动态规划统计有多少长度为t的路径

附加条件: 不能走过一条边以后又立刻反着走一次

如果没有附加条件,用邻接矩阵加速即可

那么如何满足这个附加条件呢?

我们设f[i][j]表示第i个时刻在第j条有向边终点的方案数,这样就可以保证不会反着走

然后构建邻接表,枚举点,更新加速矩阵信息

初始矩阵为所有与起始点直接连接的边

答案为所有与结束点连接的边的答案之和

详细可以查看代码

avatar
zc
2020-10-06 10:38:49

查看原题

点击跳转

可以发现除了x地图,其他地图都只有两种状态,

如果没有x地图,那就是2-sat裸题,

x地图最多只有8张,我们可以暴力枚举x地图

avatar
zc
2020-10-06 00:18:02

查看原题

点击跳转

首先每条边(x,y)至少有一个端点是关键点

条件 连边
x,y任选一个 \neg x\to y,\neg y\to x

接下来是对每部分进行连边

若将每个点向该部分中出它以外的所有点连边,复杂度为\mathcal O(n^2)

我们可以前缀优化建图

设该部分为a_1,a_2,\dots,a_w

对每个点a_i新增一个状态pre_{a_i}表示a_{1\sim i}中有没有被选为关键点

条件 连边
a_i,pre_{a_i}必须同时选 a_i\to pre_{a_i},\neg pre_{a_i}\to \neg a_i
pre_{a_{i-1}},pre_{a_i}必须同时选 pre_{a_{i-1}}\to pre_{a_i},\neg pre_{a_{i-1}}\to \neg pre_{a_i}
pre_{a_{i-1}},a_i不能同时选 pre_{a_{i-1}}\to \neg a_i,a_i\to \neg pre_{a_{i-1}}

这样就可以\mathcal O(n)连边了

avatar
zc
2020-10-05 16:10:20

查看原题

点击跳转

avatar
zc
2020-10-03 11:47:30

查看原题

点击跳转

1/2
Search
search