匈牙利算法 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...
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...
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-03-16
【BZOJ 1874：[BeiJing2009 WinterCamp]取石子游戏 】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16013639.html 题目链接 题目 小H和小Z正在玩一个取石子游戏。 取石子游戏的规则是这样的，每个人每次可以从一堆石子中取出若干个石子，每次取石子的个数有限制，谁不能取石子时就会输掉游戏。 小H先进行操作，他想问你他是否有必胜策略，如果有，第一步如何取石子。 思路 博弈论，考虑把题目变成Nim游戏。 把 [0,1000][0, 1000][0,1000] 按可行操作变成一个有向图，然后处理出它们的SG函数。 然后，把原先的每堆石子通过SG...
2023-11-06
上下界网络流小结
上下界网络流小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132093889 正式请看：https://oi-wiki.org/graph/flow/bound/ 无源汇上下界可行流 新建源汇 S,TS,TS,T ，若 a→ba\to ba→b 有 [c,d][c,d][c,d] 。网络流中上界肯定满足。 我们变成： S→b,cS\to b,cS→b,c a→T,ca\to T,ca→T,c a→b,c−da\to b,c-da→b,c−...
2021-12-01
割点和桥小结
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15631062.html 桥 定义 无向连通图中如果一条边断开后能使图不连通则条边就是桥。 方法 dfs+并查集 每条边只能走一次。如果搜到一个点还在访问中说明他们是双连通分量，用并查集合并。 Code 1234567891011121314151617181920void dfs(int x){ for(int g=h[x]; g; g=d[g].n) { if(c[g]) continue; ...