要么改变世界,要么适应世界
该标签下的文章

利用倍增的思想实现LCA算法

2021-05-27 16:48:50
97
算法

LCA算法指的是最近公共祖先(Lowest Common Ancestor),这里的最近指的是给定的两个点中所有的公共祖先中,距离根节点最远的节点,而且这两点到最近公共祖先的距离只和也是这两点之间的最短路径 ...

利用KM算法求解最大权匹配

2020-11-27 13:28:00
87
算法

`KM`算法是一种计算机算法,功能是求完备匹配下的最大权[匹配](https://baike.baidu.com/item/匹配/6397551)。在一个二分图内,左顶点为`X`,右顶点为`Y`,现对于每组左右连接`Xi->Yj`有权`wij`,求一种匹配使得所有`wij`的和最大 ...

匈牙利算法求解二分图的最大匹配

2020-11-27 13:24:12
115
算法

设`G=(V,E)`是一个无向图,如果顶点`V`可分割为两个互不相交的子集`(A,B)`,并且图中的每条边`(i,j)`所关联的两个顶点`i`和`j`分别属于这两个不同的顶点集`(i in A,j in B)`,则称图`G`为一个二分图。 ...