二分图中最小边覆盖=n-最大匹配
二分图中最小边覆盖=n-最大匹配
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132077398
每条边会覆盖1-2个点，我们希望最大化覆盖2个点的边。
覆盖两个点的边显然为二分图的最大匹配。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2021-11-29
【Loj #10100. 「一本通 3.6 练习 1」网络】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15620690.html 题目链接 题目就是给出一幅图，求其割点个数。 由于 n⩽100n\leqslant 100n⩽100，所以可以暴力删点。 当然也可以跑割点。 (感谢crx老师教我割点模板) 暴力Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636...
2022-04-25
【GDOI2022PJD2T4 机器人】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16191401.html D2T4 机器人 题目 刚上初一的小纯特别喜欢机器人，这周末，她报名了学校的“小机器人俱乐部”，而进入俱乐部需要通过一场考试。 考试场地可以看作一个 n×mn \times mn×m 的网格图，行从上往下标号为 1,…,n1, \dots, n1,…,n，列从左往右标号为 1,…,m1, \dots , m1,…,m。每个格子有三种可能：空地，障碍物，机器人（有且只有一个），分别用“.”、“*”、“R”表示。现在小纯需要...
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() ...
2023-09-18
拆贡献算总和（抓住双射）+竞赛图与连通分量相关计数：arc163_d
拆贡献算总和（抓住双射）+竞赛图与连通分量相关计数：arc163_d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132994501 https://atcoder.jp/contests/arc163/tasks/arc163_d 首先竞赛图有个性质： 然后有了这个性质，我们就可以考虑计数题的经典套路，拆贡献算总和。 考虑假如我们成功划分成两个集合 A,BA,BA,B ，其中一个可以为空（我们可以令 AAA 可以为空，防止算重），我们就记为算到一个新的...
2021-11-29
【Loj #10101. 「一本通 3.6 练习 2」嗅探器】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15621588.html 题目链接 首先如果一个点满足答案，则这个点一定是割点。 然后我们可以从 aaa 点开始搜，对于每一个点，如果 bbb 点在它的儿子内，说明这个点分离了 aaa 和 bbb。 如何判断 bbb 是否在它的儿子内，只需要在搜索这个儿子前后判断一下即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454...
2021-11-16
【P1772 [ZJOI2006]物流运输】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15562734.html 题目链接 一道很好的最短路+dp。 先考虑最后结果，设 dpidp_idpi 表示前 iii 天的最小费用。设 f(i,j)f(i, j)f(i,j) 为从第 iii 天到第 jjj 天都走同一条道路的最小费用。 f(i,j)f(i, j)f(i,j) 很好求，提前预处理这段时间内哪些点不能走然后再可以走的点内跑一遍最短路即可。 转移： dpi=minj=1i(dpj+f(j+1,i)×(i−(j+1)+1)+k)d...