二分图中最小边覆盖=n-最大匹配
二分图中最小边覆盖=n-最大匹配
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132077398
每条边会覆盖1-2个点，我们希望最大化覆盖2个点的边。
覆盖两个点的边显然为二分图的最大匹配。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-12-18
图论（边次数限制）转流：P3163危桥
图论（边次数限制）转流：P3163危桥 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135058446 https://www.luogu.com.cn/problem/P3163 考虑一条无向边 (u,v)(u,v)(u,v) 可走 www 次。 我们直接这样子转换 因此直接跑即可 但此题中如果我们直接源点练出去，汇点连出入，可能会算错： 如果都能流对应的流量，那么我们把 s2,t2s2,t2s2,t2 交换也可以，这显然是充要的。 因此跑两遍...
2026-07-25
推性质转为2-sat问题：26暑杭电2-01
推性质转为2-sat问题：26暑杭电2-01 1001 xyz 问题 我们发现这个op有3个选择，是个3-sat问题，非常麻烦。 我们分析一下性质： 发现： 在 y=1,z=0y=1,z=0y=1,z=0 时，op只能是 ^ 和 & 否则，op选 | 一定比 ^ 更优，所以op只能是 | 和 & 现在op必然是二选一了 然后我们就暴力枚举4种情况： 如果 x=i,op=jx=i,op=jx=i,op=j 不成立，则： x=1−ix=1-ix=1−i 和 op=1−jop=1-jop=1−j 至少一个成立 就转化为2-sat问题了。 1234567891011...
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; ...
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−...
2022-06-07
欧拉图和欧拉回路判定小结
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16352894.html 注意：下面讨论中的连通是不考虑孤立点的 无向图判欧拉图 连通 所有点度数为偶数 无向图判欧拉路径 连通 可以有两个点度数，其它点度数为偶数 有向图判欧拉图 基图连通（有向边不考虑方向连通） 所有点入度等于出度 有向图判欧拉路径 基图连通 允许有一个点入度比出度大于且同时有个点出度比入度大1，其他点度数为偶数
2023-08-27
匈牙利算法 in 二分图匹配
匈牙利算法 in 二分图匹配 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132517702 https://www.luogu.com.cn/problem/P3386 重新看这个算法，才发现自己没有理解。 左边的点轮流匹配，看是否能匹配成功。对右边的点进行记录 是否尝试过 然后有空就进，别人能退的就进 遍历左部点： 尝试匹配过程：