竞赛图缩点后成链状（拓扑序唯一）
竞赛图缩点后成链状（拓扑序唯一）
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132993089
一个常见结论
竞赛图缩点后必然成链状。
不是真正的链，只是类似链的偏序关系。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-18
拆贡献算总和（抓住双射）+竞赛图与连通分量相关计数：arc163_d
拆贡献算总和（抓住双射）+竞赛图与连通分量相关计数：arc163_d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132994501 https://atcoder.jp/contests/arc163/tasks/arc163_d 首先竞赛图有个性质： 然后有了这个性质，我们就可以考虑计数题的经典套路，拆贡献算总和。 考虑假如我们成功划分成两个集合 A,BA,BA,B ，其中一个可以为空（我们可以令 AAA 可以为空，防止算重），我们就记为算到一个新的...
2022-04-25
【GDOI2022PJD2T4 机器人】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16191401.html D2T4 机器人 题目 刚上初一的小纯特别喜欢机器人，这周末，她报名了学校的“小机器人俱乐部”，而进入俱乐部需要通过一场考试。 考试场地可以看作一个 n×mn \times mn×m 的网格图，行从上往下标号为 1,…,n1, \dots, n1,…,n，列从左往右标号为 1,…,m1, \dots , m1,…,m。每个格子有三种可能：空地，障碍物，机器人（有且只有一个），分别用“.”、“*”、“R”表示。现在小纯需要...
2023-12-20
竞赛图及其缩点成链、强连通分量相关性质：CF1268D
竞赛图及其缩点成链、强连通分量相关性质：CF1268D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135110596 考虑如何判断一个竞赛图是否强联通。 如果一个竞赛图不强联通，说明其存在一个子图，满足这个子图没有入边 / 出边。 我们以没有出边的情况来讨论。首先大小为 nnn 的子图之间至少产生 n(n−1)2\frac {n(n-1)}22n(n−1) 个出度，因为没有出度，所以我们就令其出度为这个就行了。从贪心角度考虑，我们直接按出度排序即可。 ...
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 补集的子集。再...
2026-08-01
运用生成树+二分图进行构造：26暑杭电多校 4-02
运用生成树+二分图进行构造：26暑杭电多校 4-02 1002 B. Binary Choice 我们发现，题目已经规定了每种颜色的数量为偶数，但却没有规定每种值的数量为偶数。 但每种值的数量必须为偶数。所以我们可以先思考一下，在不理分组的情况下，是否存在一种办法每种值的个数为偶数。 一个很常见的转化是给 ai,bia_i,b_iai,bi 连边，然后让每个点的度数为偶数。 现在转化为一个图论问题。 图论问题涉及边的构造，一般用生成树。 我们随便考虑一个连通块。首先连通块边的数量必须为偶数。 我们再随便考虑一棵dfs生成树。非树边我们随便定向。定完后对于树上的节点，从叶子开始，逐步...
2021-12-02
【[ARC063C] Integers on a Tree】
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15633812.html 题目链接 对于最小的点，与它相连的没填的点中，都赋值为这个点点权+1。 这样子贪心就算旁边的点必然会比这个点大，所以+1是没错的。 最后再遍历所有边检验答案合法性。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666...