menu zcmimi's blog

arrow_back 图论

首先把连接所有i\rightarrow p_i,可以得到若干个环

kp_i=p_{p_i}后会让i指向环上从i数起的k+1个点

只需要让一个环满足条件既可以,我们可以对

zc
2020-04-28 00:27

首先我们可以只保留每个数奇数次幂的因子

第二,根据约数个数定理,因为每个数的约数不超过7,所以最多只有两个质因子

可以把选择一个数看成在这两个质因子之间的连边

如果只有一个,那么把1作为另一

zc
2020-04-26 21:16

直接按照规则建图后跑最短路 ```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define 
zc
2020-01-19 12:25

kruskal重构树

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

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

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

否则连接x,y

$krus

zcmimi
2019-12-25

建树

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

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

![](https://images.cnblogs.com/cnblogs_com/sdzwyq/

zcmimi
2019-01-30

P3953 逛公园

题意: 求dis(1,n)<=MinDis(1,n)+K的路径数

用拓

zcmimi
2019-01-21 18:36:18

差分约束的具体概念:

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

例子:

假设有3个数a,b,c

zcmimi
2018-10-27
1 / 1
Search
search