匈牙利匹配

理论知识网上有很多，只根据代码解析下：
矩阵为：（每一列代表一个男生，每一行代表一个女生，1代表匹配，0代表不匹配）
0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 \begin{matrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \end{matrix} 000111​000101​000100​111000​100000​110000​
1.id=0的男生和id=3的女生匹配，再去找id=1的男生，发现与id=3也匹配，对id=0的男生重新寻找，找到id=4的女生匹配。
2.id=2的男生和id=3的女生匹配，发现id=1的男生与id=3匹配，对id=1的男生重新寻找，找到id=5的女生匹配，且id=5的女生还未和其他人建立匹配。
3.依次类推，直至建立所有匹配关系。

class Hungary():def __init__(self,graph):self.graph = graphself.n = len(graph)self.used = Noneself.nxt = Nonedef find(self,x):for i in range(self.n):if self.graph[i][x] == 1 and self.used[i] == 0:# 找到满足匹配关系且还没有建立匹配的对象self.used[i] = 1# 还未建立匹配关系或者男生还有别的匹配对象if self.nxt[i] == -1 or self.find(self.nxt[i]):# 保存男生匹配id和女生匹配idself.nxt[x] = iself.nxt[i] = xreturn Truereturn Falsedef match(self):self.used = [False] * self.nself.nxt = [-1] * self.nfor i in range(self.n):if self.nxt[i] == -1:# self.used初始化self.used = [False] * self.nself.find(i)

匈牙利匹配

理论知识网上有很多，只根据代码解析下：
矩阵为：（每一列代表一个男生，每一行代表一个女生，1代表匹配，0代表不匹配）
0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 \begin{matrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \end{matrix} 000111​000101​000100​111000​100000​110000​
1.id=0的男生和id=3的女生匹配，再去找id=1的男生，发现与id=3也匹配，对id=0的男生重新寻找，找到id=4的女生匹配。
2.id=2的男生和id=3的女生匹配，发现id=1的男生与id=3匹配，对id=1的男生重新寻找，找到id=5的女生匹配，且id=5的女生还未和其他人建立匹配。
3.依次类推，直至建立所有匹配关系。

class Hungary():def __init__(self,graph):self.graph = graphself.n = len(graph)self.used = Noneself.nxt = Nonedef find(self,x):for i in range(self.n):if self.graph[i][x] == 1 and self.used[i] == 0:# 找到满足匹配关系且还没有建立匹配的对象self.used[i] = 1# 还未建立匹配关系或者男生还有别的匹配对象if self.nxt[i] == -1 or self.find(self.nxt[i]):# 保存男生匹配id和女生匹配idself.nxt[x] = iself.nxt[i] = xreturn Truereturn Falsedef match(self):self.used = [False] * self.nself.nxt = [-1] * self.nfor i in range(self.n):if self.nxt[i] == -1:# self.used初始化self.used = [False] * self.nself.find(i)