二分图中最小边覆盖=n-最大匹配
二分图中最小边覆盖=n-最大匹配
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132077398
每条边会覆盖1-2个点，我们希望最大化覆盖2个点的边。
覆盖两个点的边显然为二分图的最大匹配。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2021-12-01
【Loj #10104. 「一本通 3.6 练习 5」Blockade】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15629936.html 题目链接 首先这个点删去之后必然与剩下 n−1n-1n−1 个点失去相连。 如果这个点能使其它点失去相连，说明这个点为割点。 然后统计一下每个儿子与父亲的影响即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666...
2023-08-03
无源汇上下界可行流
无源汇上下界可行流 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132091530 新建两个超级源、汇点。 原先是a->b，范围[c,d]。现在变成 S->b，c a->T，c a->b，d-c ZOJ2314ReactorCooling_网络流-个人编程笔记
2021-11-29
【Loj #10102. 「一本通 3.6 练习 3」旅游航道】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15621787.html 题目链接 题目中对主要航道定义是这样的： 如果某一条航道的删除使得一些星球不能到达，那么这条航道是不能删除的，称之为「主要航道」。 这说明了什么？ 说明了主要航道就是桥。 然后题目就是求桥的个数。 模板题。 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455...
2021-11-29
【Loj #10100. 「一本通 3.6 练习 1」网络】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15620690.html 题目链接 题目就是给出一幅图，求其割点个数。 由于 n⩽100n\leqslant 100n⩽100，所以可以暴力删点。 当然也可以跑割点。 (感谢crx老师教我割点模板) 暴力Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636...
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-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...