P2071 座位安排

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

题目分析

题目的核心在于“每一排可以坐两个人”，而每个人有两个心仪的排数。如果我们将“人”看作二分图左侧的顶点，将“排数”看作右侧的顶点，那么这道题的要求就是寻找最大匹配。

由于每一排能坐两个人的限制，我们可以通过一个小技巧将其转化为标准的二分图匹配：

• 拆分节点：将每一排座位拆分为两个独立的“座位点”。例如，第 \(i\) 排可以拆分为 \(i\) 和 \(i + N\) 两个点。
• 建立连边：如果第 \(j\) 个人想坐第 \(i\) 排，我们就从人 \(j\) 向座位点 \(i\) 和座位点 \(i + N\) 各连一条边。
• 求解：对这个拥有 \(2N\) 个人的点和 \(2N\) 个座位的点的二分图，运行匈牙利算法（Hungarian Algorithm）即可。

---

C++ 代码实现

这里使用匈牙利算法（DFS 实现），逻辑清晰且易于通过。

#include <iostream>
#include <vector>
#include <cstring>using namespace std;const int MAXN = 4005; // 2N 的最大值是 4000
vector<int> adj[MAXN]; // 邻接表，存储每个人想坐的排数
int match[MAXN];       // match[i] 表示第 i 个座位点匹配的人的编号
bool vis[MAXN];        // 标记在当前 DFS 中该座位点是否被访问过
int n;// 匈牙利算法的 DFS 核心过程
bool dfs(int u) {// 遍历这个人想坐的每一排for (int row : adj[u]) {// 每一排有两个座位点：row 和 row + nint seats[2] = {row, row + n};for (int i = 0; i < 2; ++i) {int v = seats[i];if (!vis[v]) {vis[v] = true;// 如果当前座位点没被占用，或者占用它的人可以换个位置if (match[v] == 0 || dfs(match[v])) {match[v] = u;return true;}}}}return false;
}int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n;// 输入 2N 个人的愿望for (int i = 1; i <= 2 * n; ++i) {int r1, r2;cin >> r1 >> r2;adj[i].push_back(r1);adj[i].push_back(r2);}int result = 0;// 对每一个人尝试进行匹配for (int i = 1; i <= 2 * n; ++i) {memset(vis, false, sizeof(vis));if (dfs(i)) {result++;}}cout << result << endl;return 0;
}

---

代码解析

1. 数据结构：
   • adj[i] 存储第 \(i\) 个人的两个心仪排数。
   • match[v] 记录第 \(v\) 个座位（注意这里座位编号是 \(1\) 到 \(2N\)）当前坐的是哪个人。
2. 拆分技巧：
   • 在 dfs 函数中，对于输入的排数 row，我们尝试匹配座位 row 和座位 row + n。这等价于将一排拆成两个坑位。
3. 复杂度分析：
   • 时间复杂度：匈牙利算法的最坏复杂度为 \(O(V \cdot E)\)。本题中 \(V = 2N\)，每个人的边数 \(E\) 实际上只有 \(4\) 条（连向两个排，每排两个座），所以总复杂度约为 \(O(2N \times 4)\)，即 \(O(N)\) 级别。即使算上 memset 的开销，对于 \(N=2000\) 的规模也绰绰有余。
   • 空间复杂度：主要消耗在邻接表和 match 数组，为 \(O(N)\)。

注意事项

• 本题数据规模 \(N=2000\)，总人数 \(2N=4000\)，数组大小务必开够。
• 使用 ios::sync_with_stdio(false) 可以加速输入输出，防止在大规模数据下超时。