二分图几个常用结论
二分图几个常用结论
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132076492
适用：二分图
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2021-11-17
强连通缩点——dfs+并查集做法
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15569521.html 题外话 Trajan模板太难记了（对于我来说），然后我们教练就教了我一种dfs+并查集做法，感觉挺容易理解，反正以后我就会使用这个模板了。 前置芝士 强连通 如果有向图中的两个点能够互相到达，那么他们强连通。 强连通图 如果有向图中任意两点能够互相到达，那么这个图就是强连通图 强连通分量 有向图中的极大强连通图子图就是强连通分量。（就是没有包含这个强连通子图的更大强连通子图） 缩点 把每个强连通分量作为一个结点。 正文 ...
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显然。...
2021-12-04
【Loj #10008. 「一本通 1.1 练习 4」家庭作业】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15643572.html 题目链接 题目 老师在开学第一天就把所有作业都布置了，每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为 101010，要求在 666 天内交，那么要想拿到这 101010 学分，就必须在第 666 天结束前交。 每个作业的完成时间都是只有一天。例如，假设有 7 次作业的学分和完成时间如下： 作业号 期限 学分 111 111 666 222 111 7...
2022-01-24
【CF1120D Power Tree】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15839195.html 题目链接 题目 You are given a rooted tree with n n n vertices, the root of the tree is the vertex 1 1 1 . Each vertex has some non-negative price. A leaf of the tree is a non-root vertex that has degree 1 1 1 . Arkady ...
2021-12-01
【Loj #10104. 「一本通 3.6 练习 5」Blockade】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15629936.html 题目链接 首先这个点删去之后必然与剩下 n−1n-1n−1 个点失去相连。 如果这个点能使其它点失去相连，说明这个点为割点。 然后统计一下每个儿子与父亲的影响即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666...
2023-08-27
多次跑网络流（用于构造类）+霍尔定理证明可行：AGC317G
多次跑网络流（用于构造类）+霍尔定理证明可行：AGC317G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132517757 https://atcoder.jp/contests/abc317/tasks/abc317_g 一个很显然的思路，就是行向颜色连边，但约束条件展现出多个维度，所以可以考虑跑多次网络流。 但跑同样的网络流没有意义，所以每次跑完都要在残余网络上操作一下才可行。此题中，为了方便构造，就是对成功流了的边进行删除。 但多次跑网络流是否正确...