二分图几个常用结论
二分图几个常用结论
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132076492
适用：二分图
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
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 这个限制提取出来。 因为在此限制下答案不劣，所以优先枚举这个限制下的答案。 模拟费用流，所以必然有反悔贪心，分类讨论一下。 总结下来，对于模拟费用流的方法： 分类讨论...
2023-08-03
网络最大流
网络最大流 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132091032 < Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流 - 洛谷 > 先bfs分层 2.dfs增广，当前弧优化 重复以上步骤 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545...
2023-08-27
匈牙利算法 in 二分图匹配
匈牙利算法 in 二分图匹配 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132517702 https://www.luogu.com.cn/problem/P3386 重新看这个算法，才发现自己没有理解。 左边的点轮流匹配，看是否能匹配成功。对右边的点进行记录 是否尝试过 然后有空就进，别人能退的就进 遍历左部点： 尝试匹配过程：
2023-09-12
Prüfer / Prufer 序列
Prüfer / Prufer 序列 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132090250 快速跳转 P6086 【模板】Prüfer 序列 OI-wiki 结论：一个完全图的生成树个数为 nn−2n^{n-2}nn−2 注意，生成树是指无根树 构造过程 从小到大枚举叶子节点（指度数为1的点），记录其父亲。 最终为｛2，2，3，3，2｝ 考虑树如何线性建。 12345678910111213141516void sol1() ...
2022-01-24
【P5994 [PA2014]Kuglarz】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15838986.html 题目链接 题目 魔术师的桌子上有 nnn 个杯子排成一行，编号为 1,2,…,n1,2,…,n1,2,…,n，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。 花费 cijc_{ij}cij 元，魔术师就会告诉你杯子 i,i+1,…,ji,i+1,…,ji,i+1,…,j 底下藏有球的总数的奇偶性。 采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？ 思路 前缀和建图...
2023-09-18
哈密顿回路
哈密顿回路 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132992984 哈密顿回路是一个经过所有节点恰好一次的回路。 相当于把欧拉回路定义中的边变成点