zcmimi's blog

categories/算法/图论/共5篇文章

avatar
zcmimi
2020-10-02 23:34:21

SAT指Satisfiability(可满足性问题)

k-SAT指每个限制有k个条件,而当k>2时该问题为NP完全的,只能暴力

LG 4782 【模板】2-SAT 问题

n个布尔变量x_1,x_2,\dots,x_n,另有m个需要满足的条件,每个条件的形式都是「x_itrue/falsex_jtrue/false」.

比如「x_1truex_3false」、「x_7falsex_2false」。

2-SAT问题的目标是给每个变量赋值使得所有条件得到满足。

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的差

1/1
Search
search