某人力資源公司收到了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); // 初始化所有節點層次為-1level[s] = 0; // 源點層次為0q.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; // 初始化最大流為0while (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) { // 輸入部門編號直到-1preferences[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方法計算并輸出最大配對數量。
)
)
