#P7232. [2023省队模拟]换桌

    ID: 7066 传统题 1000ms 512MiB 尝试: 4 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-最小费用最大流线段树优化建图绝对值分段线性化势能优化费用流

[2023省队模拟]换桌

题目描述

有 nn 张圆桌从左到右排成一行,编号从 00 到 n−1n-1。每张桌子有 mm 个座位,按顺时针编号 00 到 m−1m-1,初始每个座位上都有一位客人。

所有客人都需要分配一个新座位,可以留在原座位。原来坐在第 ii 桌第 jj 号座位的客人,新座位所在的桌号必须在 [Li,j,Ri,j][L_{i,j},R_{i,j}] 内,可以选这些桌中的任意座位。不同客人不能使用同一个新座位。

从第 ii 桌的 xx 号座位移动到第 jj 桌的 yy 号座位,分两步计算体力消耗:

  1. 移动到第 jj 桌的 xx 号座位,消耗 2∣i−j∣2|i-j|。
  2. 沿第 jj 桌的圆周走到 yy 号座位,消耗 min⁡(∣x−y∣,m−∣x−y∣)\min(|x-y|,m-|x-y|)。

客人移动时互不影响。请计算全部客人的最小体力消耗之和。

输入格式

第一行两个整数 n,mn,m。

接下来 nn 行,每行 mm 个整数,给出矩阵 LL。随后 nn 行,每行 mm 个整数,给出矩阵 RR。

数据随机生成:每个 Li,jL_{i,j} 和 Ri,jR_{i,j} 均独立、等概率从 00 到 n−1n-1 中选取。如果 Li,j>Ri,jL_{i,j}>R_{i,j},则交换两者。

输出格式

输出最小的总消耗。如果无解,输出 no solution。

样例输入 1

2 4
0 1 1 0
1 0 1 0
0 1 1 0
1 0 1 0

样例输出 1

10

第 00 桌的 0,30,3 号和第 11 桌的 0,20,2 号客人必须留在原桌,其他人需要换桌。一个最优方案是让两桌的 11 号座位客人互换,再让第 00 桌 22 号和第 11 桌 33 号客人互换,其余人留在原座位。

样例输入 2

2 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

样例输出 2

no solution

样例输入 3

2 10
0 0 1 1 0 0 0 1 0 0
1 1 1 0 0 1 0 0 0 0
1 0 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 0 1 0

样例输出 3

22

数据范围与约定

对于全部数据,1≤n≤3001\le n\le300,1≤m≤101\le m\le10,0≤Li,j≤Ri,j≤n−10\le L_{i,j}\le R_{i,j}\le n-1。

测试点 nn 的范围
1、2 1≤n≤21\le n\le2
3–8 1≤n≤401\le n\le40
9–14 1≤n≤1001\le n\le100
15–20 1≤n≤3001\le n\le300