匈牙利算法用于任务分配

匈牙利算法是一种解决二分图最大匹配问题的算法，也可以用于解决任务分配问题。其基本思想是通过增广路来寻找增广路径，从而不断扩大匹配集合，直到无法找到增广路为止。具体步骤如下：

1.构建二分图，将任务和人分别作为左右两部分，如果一个人可以完成某项任务，则在他们之间连一条边，边的权值为完成该任务所需的报酬。

2.初始化一个大小为N的match数组，match[i]表示任务i分配给的人的编号，初始时所有元素都为-1。

3.从左部的第一个节点开始，依次遍历每个节点，对于每个节点，从它所连的所有未匹配的右部节点中选择一个节点，如果该节点未被匹配，则直接匹配；如果该节点已经被匹配，但是可以通过其他路径找到更优的匹配，则更新匹配关系。

4.如果当前节点无法匹配，则需要寻找增广路。具体来说，从当前节点开始，依次遍历与其相邻的所有节点，如果该节点未被访问过，则将其标记为已访问，并尝试在该节点的相邻节点中寻找增广路。如果找到了增广路，则更新匹配关系；否则回溯到上一个节点，继续寻找其他路径。

5.重复步骤3和4，直到无法找到增广路为止。

6.最终得到的match数组即为任务分配方案，对应的最小报酬总数为所有匹配边的权值之和。

下面是一个Python实现的例子：

def hungarian(cost):
    n = len(cost)
    match = [-1] * n
    for i in range(n):
        visited = [False] * n
        if find_path(i, cost, match, visited):
            continue
        visited[i] = True
        while True:
            slack = float('inf')
            for j in range(n):
                if visited[j]:
                    for k in range(n):
                        if not visited[k]:
                            slack = min(slack, cost[j][k] - match[j] - match[k])
            for j in range(n):
                if visited[j]:
                    match[j] += slack
                else:
                    cost[i][j] -= slack
            for j in range(n):
                if not visited[j] and cost[i][j] == 0:
                    visited[j] = True
                    if find_path(j, cost, match, visited):
                        break
            else:
                continue
            break
    return sum(cost[i][match[i]] for i in range(n) if match[i] != -1)

def find_path(i, cost, match, visited):
    n = len(cost)
    for j in range(n):
        if not visited[j] and cost[i][j] == 0:
            visited[j] = True
            if match[j] == -1 or find_path(match[j], cost, match, visited):
                match[j] = i
                return True
    return False