GoldenPotato137的小屋

缩点/强连通分量
动态规划

[Luogu P4606] [SDOI2018]战略游戏

题面 P4606 [SDOI2018]战略游戏 Solution 圆方树上圆方果, 圆方树下你和我。 圆方树前建虚树, 欢乐多又多。 . 好吧,我们来说正题。 这题就比较强。根据常识,如果我们爆掉的点能影响这个图的连通性,那么,这个点一定是割点。 因此,我们要先对原图做Tarjan求点双。接下来,我们考虑用圆方树来解决一个问题。 我们先考虑暴力怎么做,我们先对原图求出圆方树。接下来,我们发现,对答案有贡献的点一定是孩子有被选定的点的圆点,并且这个点的总共被选定的孩子数不等于总共被选定数(因为如果这个点被割掉了,其被…

2019年4月8日 0条评论 1053点热度 1人点赞 GoldenPotato137 阅读全文
图论

[Luogu P3469] [POI2008]BLO-Blockade (割点)

题面 传送门:洛谷 Solution 先跟我大声念: $\huge poi!$ . 然后开始干正事。 首先,我们先把题目中的点分为两类:去除这个点能把图分为几个部分的,去除这个点不影响整个图的连通性的。 如下图: 点上的数字表示这个点的搜索序。 我们称这些对连通性有影响的点为割点。 先假设我们能求出这些点以及其出去后把图分为几块之后那几块分别的大小。 是不是发现了什么? 对于非割点,答案显然是$2*(n-1)$ (因为它不能影响别的点对连通性,能影响的只是别人到它以及它到别人) 对于割点,它把那几块弄得无法联通,即…

2019年2月19日 1条评论 1079点热度 0人点赞 GoldenPotato137 阅读全文
DAG DP

[Luogu P3119] [USACO15JAN]草鉴定Grass Cownoisseur

题面 传送门:洛谷 Solution 这题显然要先把缩点做了。 然后我们就可以考虑如何处理走反向边的问题。 像我这样的蒟蒻,当然是使用搜索,带记忆化的那种(滑稽)。 考虑设$f(i,j)$表示到达第i个点,还能走j次反向边,所能到达的最多的点的数量。 转移可以表示为: 如果x能到达1所在的强连通分量或max出来的值不为0,说明当前状态可行,否则不可行。 然后用记忆化搜索表达出来就OK了 Code #include<iostream> #include<cstdio> #include<…

2019年2月17日 0条评论 791点热度 0人点赞 GoldenPotato137 阅读全文
图论

[Luogu P2341] [HAOI2006]受欢迎的牛

题面 传送门:洛谷 Solution 前排提示,本蒟蒻做法既奇葩又麻烦 我们先可以把题目转换一下。 可以把一头牛喜欢另外一头牛理解为另外一头牛被一头牛喜欢。 我们把被喜欢的关系建边,即B被A喜欢,从B向A连一条有向边。 显然,一个点若能到达其他所有节点,它就是题目中的明星牛。 接下来,我们可以考虑一个类似于DP的做法。 即一个点能访问到的点,等同于它的儿子们访问的到的点加上它自己。 显然,这种特性要在DAG(有向无环图)上才能方便的使用。 所以说,我们第一步要对题目做的是缩点。 缩完点之后,我们就可以进行图上DP了…

2019年2月15日 0条评论 634点热度 0人点赞 GoldenPotato137 阅读全文

GoldenPotato137

LLer/ACMer/HITer/数院菜鸡/ECS折磨中

最近评论
hilaolu 发布于 1 年前(03月16日) 球球屑gp翻我展示一下ua屑屑
Guava 发布于 1 年前(11月30日) @GoldenPotato137 暂时是 guavaoj.tk
碱式碳酸希 发布于 1 年前(11月30日) 可以先不要告诉老师们吗(偷偷搞的
碱式碳酸希 发布于 2 年前(11月04日) %%%%Tql 请求搬运至NNEZ校内OJ公告中。 展示链接: 请在启天楼内网中访问! :razz:...
630分苦苦挣扎的菜鸡土豆 发布于 2 年前(05月01日) 肥肠抱歉,刚刚看见呢。 那个发送留言不能立刻看见源于我站挂了个腾讯云cdn,默认会返缓存的内容qwq...
分类
  • CDQ分治
  • DAG DP
  • DP+DP
  • FFT/NTT
  • Kruskal重构树
  • LCT
  • LUCAS
  • NNEZ
  • set
  • splay
  • 主席树
  • 二分/二分答案
  • 位运算
  • 倍增
  • 其他
  • 分块
  • 动态规划
  • 卷积
  • 反演
  • 同余
  • 后缀数组
  • 后缀自动机
  • 哈希
  • 图论
  • 圆方树
  • 堆
  • 多项式
  • 字符串
  • 学习笔记
  • 容斥
  • 容斥
  • 左偏树
  • 并查集
  • 数位DP
  • 数学
  • 数据结构
  • 整体二分
  • 斯特林数
  • 最小割
  • 最短路径
  • 未分类
  • 树套树
  • 树形DP
  • 模拟
  • 深度学习
  • 游记/自闭记/滚粗记
  • 点分治
  • 状压DP
  • 生涯纪录
  • 线段树
  • 组合数学
  • 缩点/强连通分量
  • 网格DP
  • 网络最大流
  • 网络流
  • 背包DP
  • 虚树
  • 贪心
  • 边双/点双
归档
  • 2022年1月
  • 2021年9月
  • 2021年3月
  • 2021年2月
  • 2019年11月
  • 2019年4月
  • 2019年3月
  • 2019年2月

COPYRIGHT © 2022 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

桂ICP备20002051号