欧拉图和欧拉回路判定小结
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16352894.html
注意：下面讨论中的连通是不考虑孤立点的
无向图判欧拉图
- 连通
- 所有点度数为偶数
无向图判欧拉路径
- 连通
- 可以有两个点度数，其它点度数为偶数
有向图判欧拉图
- 基图连通（有向边不考虑方向连通）
- 所有点入度等于出度
有向图判欧拉路径
- 基图连通
- 允许有一个点入度比出度大于且同时有个点出度比入度大1，其他点度数为偶数
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-11-07
耳分解与双极定向
耳分解与双极定向 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132112802 耳分解 对于无向图中的任意边双和有向图中的任意强联通都可以按照此方法构造： S={u}S=\{u\}S={u} 每次找 SSS 的两个元素 u,vu,vu,v （可相同），找一条 不经过 SSS 的路径 ，并把路劲上的所有点加入 SSS 可以拿来dp，来构造某种条件的边双。 常用的状态设计 f(S)f(S)f(S) ，然后枚举 TTT 为 SSS 补集的子集。再...
2023-08-04
分类讨论+反悔贪心来实现模拟费用流：[NOI2019] 序列
分类讨论+反悔贪心来实现模拟费用流：[NOI2019] 序列 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132112120 https://www.luogu.com.cn/problem/P5470 很容易把费用流建出来。 然后要模拟这个过程，把核心要点，也就是 K−LK-LK−L 这个限制提取出来。 因为在此限制下答案不劣，所以优先枚举这个限制下的答案。 模拟费用流，所以必然有反悔贪心，分类讨论一下。 总结下来，对于模拟费用流的方法： 分类讨论...
2021-11-28
【Loj #10098. 「一本通 3.6 例 1」分离的路径】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15615609.html 题目链接 首先，环内的节点必然可以至少存在两条路径到达，所以我们不用考虑环内的节点，可以先对无向图缩点。 剩下的节点必然构成一棵树，我们只需要将叶子节点两两配对。因为这样其上面的所有父亲节点都可以通过它下面的叶子节点形成环。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515...
2023-08-03
网络最大流
网络最大流 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132091032 < Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流 - 洛谷 > 先bfs分层 2.dfs增广，当前弧优化 重复以上步骤 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545...
2022-05-10
【一本通 1494：【例 1】Sightseeing Trip】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16254702.html 题目链接 题目 原题来自：CEOI 1999 给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。若无解，输出 No solution.。图的节点数不超过 100。 思路 先不管方案，就是一个无向图求最小环问题。 那就是一个floyd，每一次把 kkk 作为中转点前，先去统计与 ...
2026-08-01
运用生成树+二分图进行构造：26暑杭电多校 4-02
运用生成树+二分图进行构造：26暑杭电多校 4-02 1002 B. Binary Choice 我们发现，题目已经规定了每种颜色的数量为偶数，但却没有规定每种值的数量为偶数。 但每种值的数量必须为偶数。所以我们可以先思考一下，在不理分组的情况下，是否存在一种办法每种值的个数为偶数。 一个很常见的转化是给 ai,bia_i,b_iai,bi 连边，然后让每个点的度数为偶数。 现在转化为一个图论问题。 图论问题涉及边的构造，一般用生成树。 我们随便考虑一个连通块。首先连通块边的数量必须为偶数。 我们再随便考虑一棵dfs生成树。非树边我们随便定向。定完后对于树上的节点，从叶子开始，逐步...