二分图几个常用结论
二分图几个常用结论
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132076492
适用：二分图
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-08-27
多次跑网络流（用于构造类）+霍尔定理证明可行：AGC317G
多次跑网络流（用于构造类）+霍尔定理证明可行：AGC317G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132517757 https://atcoder.jp/contests/abc317/tasks/abc317_g 一个很显然的思路，就是行向颜色连边，但约束条件展现出多个维度，所以可以考虑跑多次网络流。 但跑同样的网络流没有意义，所以每次跑完都要在残余网络上操作一下才可行。此题中，为了方便构造，就是对成功流了的边进行删除。 但多次跑网络流是否正确...
2023-08-03
欧拉回路/路径求法
欧拉回路/路径求法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132082624 以任意一点/奇数度点开始dfs，能走就走，遍历所有边，离开时加入点。 1234567void dfs(int x) { for(; t[x]<G[x].size(); ) { int y=G[x][t[x]]; ++t[x]; dfs(y); } z.push(x); }
2026-06-18
一般图的点的三元问题转化为二分图最大独立集：ABC461G
一般图的点的三元问题转化为二分图最大独立集：ABC461G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162103270 https://atcoder.jp/contests/abc461/tasks/abc461_g 一种错误做法 我刚开始的做法： 首先每个点肯定是0、1013、2026，即0、1、2的。 考虑到每个点双内，它的最大值必然不会超过所有点选1。 于是建立圆方树，然后树上dp。 一个点若为2，则需同一点双内所有点均为0。 12345678...
2021-11-27
【P2194 HXY烧情侣】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15612746.html 题目链接 看题，发现是一个缩点。 缩完点后，对于每一个强连通分量，取其汽油费的最小值，最小值的和就是答案。 方案就是每个强连通分量最小值个数相乘。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071...
2023-08-27
匈牙利算法 in 二分图匹配
匈牙利算法 in 二分图匹配 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132517702 https://www.luogu.com.cn/problem/P3386 重新看这个算法，才发现自己没有理解。 左边的点轮流匹配，看是否能匹配成功。对右边的点进行记录 是否尝试过 然后有空就进，别人能退的就进 遍历左部点： 尝试匹配过程：
2021-12-02
【[ARC063C] Integers on a Tree】
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15633812.html 题目链接 对于最小的点，与它相连的没填的点中，都赋值为这个点点权+1。 这样子贪心就算旁边的点必然会比这个点大，所以+1是没错的。 最后再遍历所有边检验答案合法性。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666...