这道题目是经典的二分图匹配问题，但在处理大规模数据（\(N \le 10^6\)）时，需要一些巧妙的建模和优化技巧。作为信奥教练，我建议从二分图的本质出发来理解这道题。
题目分析
每个装备有两个属性值 \((a, b)\)，但只能二选一。我们需要从属性值 \(1\) 开始，依次为每个值找到一个“可用”的装备。
- 左侧集合：属性值 \(1, 2, 3, \dots\)
- 右侧集合：编号为 \(1, 2, \dots, N\) 的装备。
- 连边：如果装备 \(i\) 有属性 \(a\) 和 \(b\)，则连边 \((a, i)\) 和 \((b, i)\)。
我们的目标是：从属性 \(1\) 开始进行匹配，一旦某个属性无法找到匹配的装备，游戏结束。
解题方案：匈牙利算法
虽然 \(N\) 达到了 \(10^6\)，但由于每个属性值对应的装备选择非常有限（每个装备只有两个属性），图的结构其实很稀疏。使用匈牙利算法时，配合时间戳优化可以有效避免重复初始化 vis 数组，从而在规定时间内通过。
代码实现 (C++)
#include <iostream>
#include <vector>using namespace std;const int MAXV = 1000005; // 属性值范围，根据题目实际要求设定
const int MAXN = 1000005; // 装备数量vector<int> adj[MAXV];
int match[MAXN]; // match[i] 表示第 i 个装备匹配的属性值
int vis[MAXN]; // vis[i] 记录第 i 个装备在当前轮次是否被访问
int timer = 0;bool dfs(int u) {for (int v : adj[u]) {if (vis[v] == timer) continue; // 时间戳优化，避免 memsetvis[v] = timer;// 如果该装备还没被占用，或者占用它的属性可以换一个装备if (!match[v] || dfs(match[v])) {match[v] = u;return true;}}return false;
}int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;int max_val = 0;for (int i = 1; i <= n; ++i) {int a, b;cin >> a >> b;adj[a].push_back(i);adj[b].push_back(i);max_val = max(max_val, max(a, b));}int ans = 0;// 必须从属性 1 开始连续匹配for (int i = 1; i <= 1000000; ++i) {timer++; // 每一轮匹配增加时间戳if (dfs(i)) {ans++;} else {break; // 一旦匹配失败，立即退出}}cout << ans << endl;return 0;
}
核心细节与优化
-
时间戳优化：
在
dfs中，传统的做法是每轮memset(vis, 0, sizeof(vis))。但在 \(10^6\) 的数据量下，这会导致 \(O(V \cdot N)\) 的复杂度，绝对会超时。通过timer递增，我们只需判断vis[v] == timer即可知道当前轮次是否访问过。 -
建模转换：
- 左侧是属性值（最多 \(10^6\) 个），右侧是装备（最多 \(10^6\) 个）。
- 属性值 \(i\) 向能提供该属性的装备连边。
-
空间问题：
vector<int> adj[MAXV]在某些空间限制极严的题目中可能会 MLE。如果空间受限，建议改用链式前向星。
进阶思考：并查集解法（更高效）
这道题其实还有一个更精妙的 并查集 (DSU) 解法。
- 把属性值看作点，每个装备 \((a, b)\) 看作一条连接点 \(a\) 和 \(b\) 的边。
- 对于每个连通分量：
- 如果该分量中包含环（边数 \(\ge\) 点数），则该分量内所有属性值都能被满足。
- 如果该分量是一棵树（边数 \(=\) 点数 \(- 1\)），则该分量内除了最大的那个属性值，其余都能被满足。
- 这种方法的时间复杂度接近 \(O(N)\)，比匈牙利算法更具优势。