某人力资源公司收到了m个合格的求职者的简历，要将他们分发给n个部门，每份简历符合一个或者几个部门的要求，但是每个人的简历最多送给k个部门，每个部门最多可以接受d份简历，如何实现求职者和部门之间的最大配对。使用了最大流算法来解决问题，其中将每份简历最多送给k个部门和每个部门最多接受d份简历的问题通过构建一个流网络来解决。我们使用Ford-Fulkerson算法来实现这个最大流问题的解决。
#include <iostream> // 包含输入输出流库
#include <vector> // 包含vector容器库
#include <cstring> // 包含C风格字符串处理函数
#include <queue> // 包含队列数据结构
#include <algorithm> // 包含常用算法函数，如min
using namespace std; // 使用标准命名空间
class MaxFlow { // 定义最大流类
struct Edge { // 定义边结构
int to, capacity, flow, rev; // 目标节点、容量、流量、反向边索引
};
int n; // 节点数
vector<vector<Edge>> adj; // 邻接表表示图
vector<int> level; // 节点层次
vector<int> ptr; // 当前弧指针
bool bfs(int s, int t) { // 宽度优先搜索构建层次图
queue<int> q; // 创建队列
level.assign(n, -1); // 初始化所有节点层次为-1
level[s] = 0; // 源点层次为0
q.push(s); // 源点入队
while (!q.empty()) { // 当队列非空时
int u = q.front(); // 取出队首元素
q.pop(); // 队首元素出队
for (const Edge& e : adj[u]) { // 遍历u的所有邻边
if (level[e.to] == -1 && e.flow < e.capacity) { // 如果目标节点未访问且边未满
level[e.to] = level[u] + 1; // 设置目标节点层次
q.push(e.to); // 目标节点入队
}
}
}
return level[t] != -1; // 返回是否存在增广路径
}
int dfs(int u, int t, int pushed) { // 深度优先搜索寻找增广路径
if (pushed == 0 || u == t) return pushed; // 如果到达终点或没有可增广的流量，返回
for (int& cid = ptr[u]; cid < adj[u].size(); ++cid) { // 遍历u的所有邻边
Edge& e = adj[u][cid]; // 获取当前边
int v = e.to; // 获取目标节点
if (level[u] + 1 == level[v] && e.flow < e.capacity) { // 如果是下一层且边未满
int tr = dfs(v, t, min(pushed, e.capacity - e.flow)); // 递归寻找增广路径
if (tr == 0) continue; // 如果没有找到增广路径，继续下一条边
e.flow += tr; // 正向边增加流量
adj[v][e.rev].flow -= tr; // 反向边减少流量
return tr; // 返回增广流量
}
}
return 0; // 没有找到增广路径，返回0
}
public:
MaxFlow(int n) : n(n), adj(n), level(n), ptr(n) {} // 构造函数初始化
void addEdge(int u, int v, int capacity) { // 添加边
Edge a = {v, capacity, 0, adj[v].size()}; // 创建正向边
Edge b = {u, 0, 0, adj[u].size()}; // 创建反向边
adj[u].push_back(a); // 添加正向边
adj[v].push_back(b); // 添加反向边
}
int getMaxFlow(int s, int t) { // 计算最大流
int maxFlow = 0; // 初始化最大流为0
while (bfs(s, t)) { // 当存在增广路径时
ptr.assign(n, 0); // 重置当前弧指针
while (int flow = dfs(s, t, INT_MAX)) { // 寻找增广路径
maxFlow += flow; // 累加增广流量
}
}
return maxFlow; // 返回最大流
}
};
int main() {
int m, n, k, d; // 定义变量：求职者数量、部门数量、最多投递数、最多接受数
cout << "请输入求职者数量 m: "; // 提示输入求职者数量
cin >> m; // 输入求职者数量
cout << "请输入部门数量 n: "; // 提示输入部门数量
cin >> n; // 输入部门数量
cout << "请输入每个求职者最多投递的部门数量 k: "; // 提示输入最多投递数
cin >> k; // 输入最多投递数
cout << "请输入每个部门最多接受的简历数量 d: "; // 提示输入最多接受数
cin >> d; // 输入最多接受数
vector<vector<int>> preferences(m); // 创建二维vector存储求职者偏好
cout << "请输入每个求职者的部门偏好（每行以空格分隔的部门编号，使用-1结束）:\n"; // 提示输入偏好
for (int i = 0; i < m; ++i) { // 遍历每个求职者
int dept; // 临时存储部门编号
while (cin >> dept && dept != -1) { // 输入部门编号直到-1
preferences[i].push_back(dept); // 将部门编号添加到偏好列表
}
}
int source = 0; // 源点编号
int sink = m + n + 1; // 汇点编号
MaxFlow maxFlow(m + n + 2); // 创建最大流对象
for (int i = 0; i < m; ++i) { // 遍历每个求职者
maxFlow.addEdge(source, i + 1, k); // 添加源点到求职者的边
}
for (int i = 0; i < n; ++i) { // 遍历每个部门
maxFlow.addEdge(m + 1 + i, sink, d); // 添加部门到汇点的边
}
for (int i = 0; i < m; ++i) { // 遍历每个求职者
for (int dept : preferences[i]) { // 遍历求职者的偏好部门
maxFlow.addEdge(i + 1, m + 1 + dept, 1); // 添加求职者到部门的边
}
}
int maxMatching = maxFlow.getMaxFlow(source, sink); // 计算最大流
cout << "最大配对数量: " << maxMatching << endl; // 输出最大配对数量
return 0; // 程序正常结束
}MaxFlow类实现了最大流算法，包括构造函数、添加边的方法和计算最大流的方法。bfs方法用于构建层次图，dfs方法用于寻找增广路径。main函数读取输入，包括求职者数量、部门数量、每个求职者最多投递的部门数量和每个部门最多接受的简历数量。- 使用邻接表存储图，并添加相应的边。
- 最后调用
getMaxFlow方法计算并输出最大配对数量。
在求职者和部门之间最大配对的问题中，如果简历和部门的要求不是匹配与否，而是有一个介于0和1之间的匹配度，我们可以使用一种称为“加权二分图最大匹配”的算法。这个问题可以转化为一个最大权匹配问题，可以使用匈牙利算法或KM算法（Kuhn-Munkres）来解决。
基本思路
- 建模问题： 将求职者和部门建模为一个二分图，边的权重为匹配度。
- KM算法： 通过KM算法求解最大权匹配问题。
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 500; // 假设最大顶点数为500
const int INF = 1e9; // 一个很大的值，表示无穷大
class KM {
int n; // 顶点数量
vector<vector<double>> weights; // 权重矩阵
vector<double> lx, ly; // 顶点标号
vector<int> match; // 匹配结果
vector<bool> S, T; // S集合和T集合
vector<double> slack; // 松弛变量
vector<int> slackx; // 松弛变量对应的x
bool bfs(int u) {
S[u] = true; // 标记u属于S集合
for (int v = 0; v < n; ++v) {
if (T[v]) continue;
double delta = lx[u] + ly[v] - weights[u][v];
if (abs(delta) < 1e-9) { // 绝对值比较，防止浮点数精度问题
T[v] = true; // 标记v属于T集合
if (match[v] == -1 || bfs(match[v])) {
match[v] = u;
return true;
}
} else {
if (slack[v] > delta) {
slack[v] = delta;
slackx[v] = u;
}
}
}
return false;
}
void update() {
double delta = INF;
for (int v = 0; v < n; ++v) {
if (!T[v]) {
delta = min(delta, slack[v]);
}
}
for (int i = 0; i < n; ++i) {
if (S[i]) lx[i] -= delta;
if (T[i]) ly[i] += delta;
if (!T[i]) slack[v] -= delta;
}
}
public:
KM(int n) : n(n), weights(n, vector<double>(n)), lx(n), ly(n), match(n, -1), S(n), T(n), slack(n), slackx(n) {}
void setWeight(int u, int v, double w) {
weights[u][v] = w;
}
double maxWeightMatching() {
for (int i = 0; i < n; ++i) {
lx[i] = *max_element(weights[i].begin(), weights[i].end());
}
for (int u = 0; u < n; ++u) {
fill(slack.begin(), slack.end(), INF);
while (true) {
fill(S.begin(), S.end(), false);
fill(T.begin(), T.end(), false);
if (bfs(u)) break;
update();
}
}
double result = 0;
for (int v = 0; v < n; ++v) {
if (match[v] != -1) {
result += weights[match[v]][v];
}
}
return result;
}
};
int main() {
int m, n;
cout << "请输入求职者数量 m: ";
cin >> m;
cout << "请输入部门数量 n: ";
cin >> n;
KM km(max(m, n)); // 创建KM算法对象，顶点数量为求职者和部门数量中的较大值
cout << "请输入匹配度矩阵（" << m << "行" << n << "列，介于0和1之间）:\n";
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
double weight;
cin >> weight;
km.setWeight(i, j, weight);
}
}
double maxMatching = km.maxWeightMatching();
cout << "最大匹配度: " << maxMatching << endl;
return 0;
}
代码解释
- KM类： 实现了Kuhn-Munkres算法。包括初始化、设置权重和求解最大权匹配的功能。
- bfs函数： 使用广度优先搜索寻找增广路径。
- update函数： 更新顶点标号，调整松弛变量。
- maxWeightMatching函数： 计算最大权匹配。
- main函数： 读取输入，创建KM算法对象，设置权重矩阵，并计算最大权匹配。
