二分图

发表于2021-02-18|更新于2023-08-02|oi学习笔记图论

|总字数:135|浏览量:

二分图的结论和算法 ~~防止忘记~~

匈牙利算法的过程是，枚举每一个左部点 $u$ ，然后枚举该左部点连出的边，对于一个出点 $v$ ，如果它没有被先前的左部点匹配，那么直接将 $u$ 匹配 $v$ ，否则尝试让 $v$ 的“原配”左部点去匹配其他右部点，如果“原配”匹配到了其他点，那么将 $u$ 匹配 $v$ ，否则 $u$ 失配。
二分图最大独立集等于总点数减去最大匹配

文章作者: Cauphenuny

文章链接: https://cauphenuny.github.io/2021/02/18/bipartite-graph/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Cauphenuny's Blog！

图论二分图

相关推荐

20210218 模拟赛总结

Index Review 考的不错，主要是第一题做出来了，分数可观， 140pts。但是后面两题的暴力分也没有打满，这是做的不够的一点。 Solution pk 定义 f(n,k)=(n−k+1)!∑i=0k−1(n−ki)(kj−i−1)f(n,k)=(n-k+1)!\sum_{i=0}^{k-1}\dbinom{n-k}{i}\dbinom{k}{j-i-1}f(n,k)=(n−k+1)!∑i=0k−1(in−k)(j−i−1k) ，求 ∑i=LRf(i+s,i)\sum\limits_{i=L}^{R}f(i+s,i)i=L∑Rf(i+s,i) 经过打表可以发现 f(n,n)=nf(n,n)=nf(n,n)=n 和 f(n,k)=f(n,k+1)⋅kf(n,k)=f(n,k+1)\cdot kf(n,k)=f(n,k+1)⋅k 化简得 f(n,k)=n!(k−1)!f(n,k)=\dfrac{n!}{(k-1)!}f(n,k)=(k−1)!n! type=1 首先考虑 type=1 的情况，代入式子即得...

评论

数据加载中