座位分配的最小体力消耗问题题解

题目分析

题目要求为 $n$ 张圆桌（每张 $m$ 个座位）的客人分配新座位，满足第 $i$ 桌第 $j$ 人的新座位在 $[L_{i,j}, R_{i,j}]$ 桌范围内，且总体力消耗最小。体力消耗分为两部分：

1. 桌间移动：$2 \times |i-j|$（$i$ 为原桌，$j$ 为目标桌）；
2. 桌内移动：$\min(|x-y|, m-|x-y|)$（$x$ 为目标桌对应座位，$y$ 为最终座位）。

核心难点在于：

• 需同时满足“桌范围约束”和“座位一一匹配”（每张桌子的 $m$ 个座位必须被恰好分配一次）；
• 体力消耗的非线性（桌内移动的最小距离）需转化为图论模型的线性代价。

核心思路

1. 最小费用最大流（MCMF）建模

将问题转化为二分图匹配问题，通过最小费用最大流求解：

• 节点定义：
  • 源点 $s$、汇点 $t$；
  • $b[i][j]$：代表第 $i$ 桌第 $j$ 个客人的出发节点；
  • $a[i][j]$：代表第 $i$ 桌第 $j$ 个座位的接收节点。
• 边的构建：
  1. 源点 $s$ 到每个 $b[i][j]$ 连边，容量 $1$，费用 $0$（每个客人必须分配一个座位）；
  2. 每个 $a[i][j]$ 到汇点 $t$ 连边，容量 $1$，费用 $0$（每个座位必须被分配一次）；
  3. 桌内座位间连边：$a[i][j]$ 与 $a[i][(j+1)\%m]$ 互连，容量 $\text{INF}$，费用 $1$（模拟桌内最小移动距离）；
  4. 客人到目标桌的连边：通过线段树优化建图，将客人到区间 $[L_{i,j}, R_{i,j}]$ 的桌间移动代价转化为边的费用。

2. 线段树优化建图

由于 $n$ 最大为 $300$，直接为每个客人连边到 $[L_{i,j}, R_{i,j}]$ 内的所有桌会导致边数爆炸，因此：

• 构建两棵线段树（$sx$、$sy$），分别处理“从左到右”和“从右到左”的桌间移动代价；
• 线段树的每个节点代表一个桌区间，父节点向子节点连边，费用为区间移动的体力消耗；
• 客人节点通过线段树节点间接连到目标桌的座位节点，将区间连边转化为 $O(\log n)$ 条边。

3. 代价建模细节

• 桌间移动代价：$2 \times |i-j|$ 被拆分为“左移”和“右移”两种情况，分别通过 $sx$ 和 $sy$ 线段树的边费用体现；
• 桌内移动代价：通过环形连边（$a[i][j]$ 与相邻座位互连），让流自动选择最小移动路径，费用为 $1$ 对应单位移动消耗。

解题步骤

1. 节点初始化

为每个客人（$b[i][j]$）和每个座位（$a[i][j]$）分配唯一的节点编号，初始化源点 $s$ 和汇点 $t$。

2. 线段树构建

• 构建 $sx$（左移）和 $sy$（右移）两棵线段树，每个节点对应桌区间，父节点向子节点连边并设置对应费用；
• 线段树的叶子节点对应具体桌的座位节点 $a[i][j]$。

3. 边的连接

• 源点到客人节点、座位节点到汇点的基础边；
• 桌内座位的环形连边；
• 客人节点通过线段树连到目标桌区间，根据客人原桌与目标区间的位置关系（左/右/包含），选择 $sx$ 或 $sy$ 线段树连接。

4. 求解最小费用最大流

运行 MCMF 算法，若最大流为 $n \times m$（所有客人和座位匹配），则输出最小费用；否则输出 no solution。

复杂度分析

• 节点数：$O(nm + n \log n)$（客人/座位节点 + 线段树节点）；
• 边数：$O(nm \log n + n \log n)$（基础边 + 线段树边 + 客人到线段树的边）；
• MCMF 复杂度：采用原始对偶算法，时间复杂度为 $O(F \times E \log V)$（$F = nm$ 为流量，$E$ 为边数，$V$ 为节点数），适配 $n \le 300, m \le 10$ 的数据范围。

总结

本题的核心是将组合优化问题转化为最小费用最大流模型，并通过线段树优化建图解决大规模区间连边问题：

1. 利用 MCMF 天然适配“一一匹配 + 代价最小”的需求，将客人和座位建模为流网络的节点；
2. 线段树优化将区间连边的 $O(n)$ 复杂度降为 $O(\log n)$，突破了直接建图的效率瓶颈；
3. 桌内移动的环形连边设计，巧妙将“最小距离”约束转化为流的路径选择，无需显式枚举所有可能的座位移动。

这种“问题建模 + 数据结构优化”的思路是解决大规模图论问题的典型方法，关键在于将实际约束转化为图的边/节点属性，同时通过优化建图降低算法复杂度。