哈密顿回路
哈密顿回路
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132992984
哈密顿回路是一个经过所有节点恰好一次的回路。
相当于把欧拉回路定义中的边变成点
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-08-27
匈牙利算法 in 二分图匹配
匈牙利算法 in 二分图匹配 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132517702 https://www.luogu.com.cn/problem/P3386 重新看这个算法，才发现自己没有理解。 左边的点轮流匹配，看是否能匹配成功。对右边的点进行记录 是否尝试过 然后有空就进，别人能退的就进 遍历左部点： 尝试匹配过程：
2021-11-29
【Loj #10101. 「一本通 3.6 练习 2」嗅探器】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15621588.html 题目链接 首先如果一个点满足答案，则这个点一定是割点。 然后我们可以从 aaa 点开始搜，对于每一个点，如果 bbb 点在它的儿子内，说明这个点分离了 aaa 和 bbb。 如何判断 bbb 是否在它的儿子内，只需要在搜索这个儿子前后判断一下即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454...
2021-12-01
【Loj #10099. 「一本通 3.6 例 2」矿场搭建】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15630249.html 题目链接 我们先对于有向图缩点，变成一棵树。 然后我们对于每个树上且在原图中的分割点节点所对应原图中的连通块考虑。 假设这里没有割点，很明显，只需要放2个出口即可。 如果有一个割点，说明这个点是树上的叶子节点，需要放1个出口。 如果有两个或以上的割点，无论哪个割点被割，都可以往另一个方向逃，所以这个连通块不用放。 Code 1234567891011121314151617181920212223242526272829...
2021-12-10
【牛客IOI周赛26-普及组 D-最短路 】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15673449.html 题目链接 题目 给定长度为 n 的数列 a，如果 （按位与），则在 i,j 之间存在一条长度为 的边，求 1 至所有点的最短路。 思路 暴力连边，边太多，最多 n2n^2n2 条，MLE+TLE。 于是考虑减少边的数量。 首先建32个虚点。 然后加入 aia_iai 在第 kkk 位上为1，就在 iii 和第 kkk 个虚点当中连边，边权为 aia_iai。 这样最多有 n×32n\times 32n×32 条边。...
2023-08-03
欧拉回路/路径求法
欧拉回路/路径求法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132082624 以任意一点/奇数度点开始dfs，能走就走，遍历所有边，离开时加入点。 1234567void dfs(int x) { for(; t[x]<G[x].size(); ) { int y=G[x][t[x]]; ++t[x]; dfs(y); } z.push(x); }
2021-12-11
【P1661 扩散】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15674805.html 题目链接 题目 一个点每过一个单位时间就会向四个方向扩散一个距离，如图。 两个点a、b连通，记作e(a,b),当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、v都必定存在路径e(u,a0),e(a0,a1),…,e(ak,v)。给定平面上的n给点，问最早什么时刻它们形成一个连通块。 思路 二分答案+并查集。 首先二分时间 ttt。 如果两个点能直接相连，则他们的曼哈顿距离小于二倍 ttt。并且把...