HalaMadrid！

二分图

tarjan算法(7) 未归档(22) 网络流(2) 读书笔记(4) 题解(11)

/ 注册

全部文章 / 二分图（共2篇）

6-（KM算法-求带权最小匹配

https://vjudge.net/problem/POJ-3565思路：所有线段都不相交，等价于让每条线段的长度之和最小至于求最小匹配，只要把边权w[][]取反，然后按求最大匹配的思路求解即可 #include<iostream> #include<cstdio> #in...

2020-11-01

0 771

算法记录-7-（二分图带权最大匹配-KM算法）

时间复杂度：O（N^4）本算法局限性较大，只能在满足“带权最大匹配一定是完备匹配”的图中正确求解，所以一般使用费用流来求解此类问题，但是本算法在求解稠密图时效率要高于费用流 const int N=105; int w[N][N]; int la[N],lb[N]; bool va[N],vb[N]...

2020-11-01

0 986