当前位置：首页 > news >正文

P2756 飞行员配对方案问题

news 2026/3/27 6:28:36

这是一道经典的二分图最大匹配问题。

题目分析

题目要求将外籍飞行员与英国飞行员进行配对，使得配对总数最大。

节点分布：左侧是 \(1\) 到 \(m\) 号外籍飞行员，右侧是 \(m+1\) 到 \(n\) 号英国飞行员。
边：如果外籍飞行员 \(u\) 能与英国飞行员 \(v\) 配合，则在 \(u\) 和 \(v\) 之间连一条边。
目标：寻找该二分图的最大匹配数，并输出具体的匹配方案。

算法选择

由于数据范围较小（\(n < 100\)），有两种主流解法：

匈牙利算法 (Hungarian Algorithm)：实现简单，处理二分图匹配非常直观，时间复杂度为 \(O(VE)\)，在本题完全绰绰有余。
网络最大流 (Dinic / ISAP)：建立超源点 \(S\) 连向所有外籍飞行员，超汇点 \(T\) 由所有英国飞行员连向，容量均为 1。飞行员之间的边容量也为 1。最大流即为最大匹配。

这里推荐使用匈牙利算法，因为它在记录匹配方案时更加方便。

C++ 代码实现（匈牙利算法）

#include <iostream>
#include <vector>
#include <cstring>using namespace std;// 全局变量定义
int m, n;
vector<int> adj[105]; // 邻接表，记录每个外籍飞行员可以配合的英国飞行员
int match[105];       // match[v] 记录英国飞行员 v 所匹配的外籍飞行员编号
bool vis[105];        // 标记在一次 DFS 中，该英国飞行员是否已被访问// 匈牙利算法核心：DFS 寻找增广路
bool dfs(int u) {for (int v : adj[u]) {if (!vis[v]) {vis[v] = true;// 如果英国飞行员 v 还没配对，或者他原配可以去找别人if (match[v] == 0 || dfs(match[v])) {match[v] = u; // 更新配对关系return true;}}}return false;
}int main() {// 1. 输入处理cin >> m >> n;int u, v;while (cin >> u >> v && (u != -1 && v != -1)) {adj[u].push_back(v); // 建立从外籍飞行员到英国飞行员的单向边即可}// 2. 循环遍历每一个外籍飞行员，尝试匹配int max_matches = 0;for (int i = 1; i <= m; ++i) {memset(vis, 0, sizeof(vis)); // 每次寻找增广路前重置访问标记if (dfs(i)) {max_matches++;}}// 3. 输出结果cout << max_matches << endl;for (int i = m + 1; i <= n; ++i) {if (match[i] > 0) {// 输出格式：外籍飞行员 英国飞行员cout << match[i] << " " << i << endl;}}return 0;
}

代码详解

图的存储：由于题目明确 \(u \le m\) 且 \(v > m\)，我们只需要建立从 \(u\) 到 \(v\) 的单向邻接表即可。
dfs(u) 函数：
- 对于外籍飞行员 \(u\)，遍历他所有能配合的英国飞行员 \(v\)。
- 如果 \(v\) 在这一轮匹配中还没被“商量”过（!vis[v]），就尝试把 \(u\) 分配给 \(v\)。
- 分配成功的条件是：\(v\) 目前单身（match[v] == 0），或者 \(v\) 的现任对象可以腾出位置（dfs(match[v])）。
统计与输出：
- max_matches 记录成功匹配的总数。
- 最后遍历 match 数组（下标为 \(m+1\) 到 \(n\)），如果 match[i] 不为 0，说明英国飞行员 \(i\) 有匹配对象。