匈牙利算法最优指派代码C++

匈牙利算法（也称为Kuhn-Munkres算法）是一种解决最优指派问题的经典算法。它可以在给定的二分图中找到一个最优的指派方案，使得总权重最小。

以下是匈牙利算法的C++代码示例：

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

// 匈牙利算法的DFS函数
bool dfs(vector<vector<int>>& graph, vector<int>& match, vector<bool>& visited, int u) {
    int n = graph.size();
    for (int v = 0; v < n; ++v) {
        if (graph[u][v] && !visited[v]) {
            visited[v] = true;
            if (match[v] == -1 || dfs(graph, match, visited, match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

// 匈牙利算法求解最优指派问题
int hungarian(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> match(n, -1);  // 存储每个顶点的匹配顶点
    int result = 0;  // 最优指派的总权重

    for (int u = 0; u < n; ++u) {
        vector<bool> visited(n, false);
        if (dfs(graph, match, visited, u)) {
            result++;
        }
    }

    return result;
}

int main() {
    // 构建二分图的邻接矩阵表示
    vector<vector<int>> graph = {
        {3, 1, 4},
        {2, 2, 3},
        {1, 3, 5}
    };

    int minWeight = hungarian(graph);
    cout << "最优指派的总权重为：" << minWeight << endl;

    return 0;
}

这段代码实现了匈牙利算法，通过构建二分图的邻接矩阵表示，并调用`hungarian`函数求解最优指派问题。最后输出最优指派的总权重。