匈牙利算法 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-08-01
运用生成树+二分图进行构造：26暑杭电多校 4-02
运用生成树+二分图进行构造：26暑杭电多校 4-02 1002 B. Binary Choice 我们发现，题目已经规定了每种颜色的数量为偶数，但却没有规定每种值的数量为偶数。 但每种值的数量必须为偶数。所以我们可以先思考一下，在不理分组的情况下，是否存在一种办法每种值的个数为偶数。 一个很常见的转化是给 ai,bia_i,b_iai,bi 连边，然后让每个点的度数为偶数。 现在转化为一个图论问题。 图论问题涉及边的构造，一般用生成树。 我们随便考虑一个连通块。首先连通块边的数量必须为偶数。 我们再随便考虑一棵dfs生成树。非树边我们随便定向。定完后对于树上的节点，从叶子开始，逐步...
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-12-01
【Loj #10104. 「一本通 3.6 练习 5」Blockade】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15629936.html 题目链接 首先这个点删去之后必然与剩下 n−1n-1n−1 个点失去相连。 如果这个点能使其它点失去相连，说明这个点为割点。 然后统计一下每个儿子与父亲的影响即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666...
2023-09-16
二分套网络流：ABC320G
二分套网络流：ABC320G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132927159 首先肯定先枚举数字 然后考虑二分答案 每个字符串向它合法的位置连边 然后易发现每个点出度最多为 nnn ，不然没意义 所以最多 O(n2)O(n^2)O(n2) 条边 然后跑网络流，看能不能流完，也就是能不能匹配成功即可 123456789101112131415161718192021222324252627282930313233343536373839404...
2021-12-09
【SSOJ2625: 哪些路不能修】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15669522.html 题目 一个有n个景点（入口）、m条单向道路的旅游胜地，单向是不友好的，因为这会让游客走很多冤枉路，而且从同一个入口出发，往不同方向走，能游玩的景点数目可能不同。于是，善良的Bob决定将道路全部改造成双向的，让每一个入口能逛的景点数量都确定下来，并制作景点数目表，让游客清楚地知道各个入口的景点数。但是，如果全部改成双向边之后，还需要修路，就可能导致景点数目表不正确。如果要景点数目表正确，请问哪些路是不能修的？ 思路 这题的...
2024-01-17
0115C补充
0115C补充 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135640069 前 ： https://blog.csdn.net/zhangtingxiqwq/article/details/135612739 这题的图是和很特殊的图，它是一个竞赛图扣去了 mmm 条边，且剩下的边满足传递封闭性。 在这种情况下，我们每个点暴力往自己可以匹配最小的点去匹配，则最多有 m\sqrt mm 个点无法匹配。（这一步的证明用到了封闭性） 对于这一步的匹配，我们可...