模板 – Tgotp-Blog

Picnic Planning(野餐计划)

最小限度生成树

c++代码如下:

 

2260: 商店购物 && 4349: 最小树形图 朱刘算法

2260的数据应该有误,存在自环,然而网上的题解一看都是一个样子。。。

简直了。。。重点是还能跑出来?!

这题就是最小树形图的板子题。

我的代码必须强行跑一次朱刘才能过2260

 

思路大致如下:
考虑到不存在自环时,每个点一定除了第一次以外均会被以最优方式[......]

Read more

虚树 模板

把要建树的点拿出来按照dfs序升序排列

用栈维护当前的链,然后因为考虑不能破坏树的结构,那么相邻两点的lca一定会插入。

因为可能有自环或者连向0点,add操作对应修改一下

简单维护即可

c++代码如下:

[......]

Read more

1823: [JSOI2010]满汉全席 2 - sat

2-sat模板题

观察发现,对于每一种食材只能选择一次,即如果你选择了一种菜,那么对于这菜所需食材的另外一种方式连向该人的另一种必需品。

这里我看hzwer的blog,感觉就有点问题,他这里是把该菜品连向另一菜品的另外一种形式,exm?难道说你就不能同时选择两种菜了么?

当然代码体[......]

Read more

#80. 二分图最大权匹配

 

c++代码如下:

 

T11837 s2 lca模板(tarjan

c++代码如下:

 

T11837 s2 lca模板(倍增版)

lca模板

第一份写萎了

c++代码如下:

当然都能ac

第二份。

实际上 路径的长度为depth[x] + depth[y] - 2* depth[lca]

c++代码如下:
[c[......]

Read more

P3381 【模板】最小费用最大流

跑spfa,然后dfs一样的步骤,不过要注意 反向边费用取反。

c++代码如下:

 

P3388 【模板】割点(割顶)

对于一个点;

满足割点的前提是,以这个点跑出去的点能找到的最小值都小于当前的dfn。

另外:如果他是根,就必须有至少两个儿子。

c++代码如下:

 

1798: [Ahoi2009]Seq 维护序列seq

注意:先乘后加!!!!QAQ

c++代码如下: