匈牙利算法 in 二分图匹配
匈牙利算法 in 二分图匹配
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132517702
https://www.luogu.com.cn/problem/P3386
重新看这个算法，才发现自己没有理解。
左边的点轮流匹配，看是否能匹配成功。对右边的点进行记录 是否尝试过
然后有空就进，别人能退的就进
遍历左部点：
尝试匹配过程：
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
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...
2026-08-01
运用生成树+二分图进行构造：26暑杭电多校 4-02
运用生成树+二分图进行构造：26暑杭电多校 4-02 1002 B. Binary Choice 我们发现，题目已经规定了每种颜色的数量为偶数，但却没有规定每种值的数量为偶数。 但每种值的数量必须为偶数。所以我们可以先思考一下，在不理分组的情况下，是否存在一种办法每种值的个数为偶数。 一个很常见的转化是给 ai,bia_i,b_iai,bi 连边，然后让每个点的度数为偶数。 现在转化为一个图论问题。 图论问题涉及边的构造，一般用生成树。 我们随便考虑一个连通块。首先连通块边的数量必须为偶数。 我们再随便考虑一棵dfs生成树。非树边我们随便定向。定完后对于树上的节点，从叶子开始，逐步...
2023-08-03
二分图中最小边覆盖=n-最大匹配
二分图中最小边覆盖=n-最大匹配 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132077398 每条边会覆盖1-2个点，我们希望最大化覆盖2个点的边。 覆盖两个点的边显然为二分图的最大匹配。
2021-12-01
【Loj #10104. 「一本通 3.6 练习 5」Blockade】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15629936.html 题目链接 首先这个点删去之后必然与剩下 n−1n-1n−1 个点失去相连。 如果这个点能使其它点失去相连，说明这个点为割点。 然后统计一下每个儿子与父亲的影响即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666...
2024-01-15
传递闭包 + dilworth定理 + 二分图求最小链覆盖 + 模拟匈牙利 ： 0115C
传递闭包 + dilworth定理 + 二分图求最小链覆盖 + 模拟匈牙利 ： 0115C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135612739 http://47.92.197.167:5283/contest/451/problem/3 求一个特殊图最大独立团，相当于是补集的最大独立集。然后这个补集（是个偏序集）满足传递闭包性质，根据 最大独立集 = 最长反链 = 最小链覆盖，题目等价于求最小链覆盖。这个可以直接网络流跑60分的。 对于正解，...
2023-09-16
可能的模拟网络流部分思路整理（CF1408H）
可能的模拟网络流部分思路整理（CF1408H） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132093428 https://www.luogu.com.cn/problem/CF1408H 先转换 模拟网络流，所以要么割最上面一层，要么割最下面一层。 对于最上一层，肯定是左边连续+右边连续。 考虑枚举左边连续，对应到某些颜色节点，又对应到某些右边节点。 对右边节点建棵线段树，由于左边的点已经确定，先假设下面的和右边的点全部割掉。 右边的点全部割掉，所以...