search

mzzr / interview

面试常见知识点整理
11 stars 3 forks source link

图 #1

Open mzzr opened 5 years ago

mzzr commented 5 years ago

二分图匹配——匈牙利算法和KM算法

最大流

  1. 关于最小费用流（minimum cost flow）的基本介绍： https://www.topcoder.com/community/competitive-programming/tutorials/minimum-cost-flow-part-one-key-concepts/

  2. 具体实现的几种方法： https://www.topcoder.com/community/competitive-programming/tutorials/minimum-cost-flow-part-two-algorithms/

  3. 应用实例，第一个就是Assignment Problem： https://www.topcoder.com/community/competitive-programming/tutorials/minimum-cost-flow-part-three-applications/

mzzr commented 5 years ago

并查集

class UnionFindSet(object):
    def __init__(self, size):
        self.d = [i for i in range(size+1)]

    def find(self, x):
        if self.d[x] != x:
            self.d[x] = self.find(self.d[x])
        return self.d[x]

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        self.d[px] = py