zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15631062.html 桥 定义 无向连通图中如果一条边断开后能使图不连通则条边就是桥。 方法 dfs+并查集 每条边只能走一次。如果搜到一个点还在访问中说明他们是双连通分量，用并查集合并。 Code 1234567891011121314151617181920void dfs(int x){ for(int g=h[x]; g; g=d[g].n) { if(c[g]) continue; ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15630249.html 题目链接 我们先对于有向图缩点，变成一棵树。 然后我们对于每个树上且在原图中的分割点节点所对应原图中的连通块考虑。 假设这里没有割点，很明显，只需要放2个出口即可。 如果有一个割点，说明这个点是树上的叶子节点，需要放1个出口。 如果有两个或以上的割点，无论哪个割点被割，都可以往另一个方向逃，所以这个连通块不用放。 Code 1234567891011121314151617181920212223242526272829...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15629936.html 题目链接 首先这个点删去之后必然与剩下 n−1n-1n−1 个点失去相连。 如果这个点能使其它点失去相连，说明这个点为割点。 然后统计一下每个儿子与父亲的影响即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15625582.html 题目链接 首先考虑删走一个点后能增加联通块数量，则这个点一定是割点。 然后就完了啊 tarjan完（虽然我没有打tarjan）我们就分别判断每个点是不是割点。如果是看一下是否有父。统计一下即可。 要注意题目一定要割，所以如果有 nnn 个联通块要输出 n−1n-1n−1。 Code 1234567891011121314151617181920212223242526272829303132333435363738394...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15621787.html 题目链接 题目中对主要航道定义是这样的： 如果某一条航道的删除使得一些星球不能到达，那么这条航道是不能删除的，称之为「主要航道」。 这说明了什么？ 说明了主要航道就是桥。 然后题目就是求桥的个数。 模板题。 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15621588.html 题目链接 首先如果一个点满足答案，则这个点一定是割点。 然后我们可以从 aaa 点开始搜，对于每一个点，如果 bbb 点在它的儿子内，说明这个点分离了 aaa 和 bbb。 如何判断 bbb 是否在它的儿子内，只需要在搜索这个儿子前后判断一下即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15620690.html 题目链接 题目就是给出一幅图，求其割点个数。 由于 n⩽100n\leqslant 100n⩽100，所以可以暴力删点。 当然也可以跑割点。 (感谢crx老师教我割点模板) 暴力Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15615609.html 题目链接 首先，环内的节点必然可以至少存在两条路径到达，所以我们不用考虑环内的节点，可以先对无向图缩点。 剩下的节点必然构成一棵树，我们只需要将叶子节点两两配对。因为这样其上面的所有父亲节点都可以通过它下面的叶子节点形成环。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15612746.html 题目链接 看题，发现是一个缩点。 缩完点后，对于每一个强连通分量，取其汽油费的最小值，最小值的和就是答案。 方案就是每个强连通分量最小值个数相乘。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600574.html 题目链接 典型的树形dp。 设 dp(x,i)dp(x, i)dp(x,i) 表示 xxx 的子树内逗留 iii 秒的作品最大值。 dp(x,i)=max⁡y∈xmax⁡i=0smax⁡j=2×zidp(y,j−2×z)−dp(x,j−i)dp(x, i)=\max_{y\in x}\max_{i=0}^s\max_{j=2\times z}^i dp(y,j-2\times z)-dp(x,j-i) dp(x,i)=y...