哈密顿回路
哈密顿回路
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132992984
哈密顿回路是一个经过所有节点恰好一次的回路。
相当于把欧拉回路定义中的边变成点
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-12-26
调整法+单调性分析（贪心）+折半状压：Cf839E
调整法+单调性分析（贪心）+折半状压：Cf839E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135224828 https://vj.imken.moe/contest/599445#problem/D 有以下结论： 带权子图必为完全图 内部点权值一定相等 点个数越多越好 对于1的证明，我们使用调整法。考虑 (x,y)(x,y)(x,y) 不连通，把 xxx 全加到 yyy 或把 yyy 全加到 xxx ，一定有一个更优。 2显然。...
2022-05-10
【一本通 1494：【例 1】Sightseeing Trip】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16254702.html 题目链接 题目 原题来自：CEOI 1999 给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。若无解，输出 No solution.。图的节点数不超过 100。 思路 先不管方案，就是一个无向图求最小环问题。 那就是一个floyd，每一次把 kkk 作为中转点前，先去统计与 ...
2023-08-10
点分治小结
点分治小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132217048 https://www.luogu.com.cn/problem/P3806 dfs1：找到当前重心 dfs2：统计当前每个点到重心的距离 dfz：点分治 找重心，处理出 xxx 所有儿子子树和非 xxx 子树的大小最大值，这个最大值最小的点 xxx 就是答案 注意这个过程中统计非 xxx 子树大小需要统计当前分治区间的大小 sumsumsum ，要时刻注意维护这个...
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。并且把...
2026-07-25
推性质转为2-sat问题：26暑杭电2-01
推性质转为2-sat问题：26暑杭电2-01 1001 xyz 问题 我们发现这个op有3个选择，是个3-sat问题，非常麻烦。 我们分析一下性质： 发现： 在 y=1,z=0y=1,z=0y=1,z=0 时，op只能是 ^ 和 & 否则，op选 | 一定比 ^ 更优，所以op只能是 | 和 & 现在op必然是二选一了 然后我们就暴力枚举4种情况： 如果 x=i,op=jx=i,op=jx=i,op=j 不成立，则： x=1−ix=1-ix=1−i 和 op=1−jop=1-jop=1−j 至少一个成立 就转化为2-sat问题了。 1234567891011...
2021-11-17
强连通缩点——dfs+并查集做法
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15569521.html 题外话 Trajan模板太难记了（对于我来说），然后我们教练就教了我一种dfs+并查集做法，感觉挺容易理解，反正以后我就会使用这个模板了。 前置芝士 强连通 如果有向图中的两个点能够互相到达，那么他们强连通。 强连通图 如果有向图中任意两点能够互相到达，那么这个图就是强连通图 强连通分量 有向图中的极大强连通图子图就是强连通分量。（就是没有包含这个强连通子图的更大强连通子图） 缩点 把每个强连通分量作为一个结点。 正文 ...