#P7232. [2023省队模拟]换桌
[2023省队模拟]换桌
题目描述
有 张圆桌从左到右排成一行,编号从 到 。每张桌子有 个座位,按顺时针编号 到 ,初始每个座位上都有一位客人。
所有客人都需要分配一个新座位,可以留在原座位。原来坐在第 桌第 号座位的客人,新座位所在的桌号必须在 内,可以选这些桌中的任意座位。不同客人不能使用同一个新座位。
从第 桌的 号座位移动到第 桌的 号座位,分两步计算体力消耗:
- 移动到第 桌的 号座位,消耗 。
- 沿第 桌的圆周走到 号座位,消耗 。
客人移动时互不影响。请计算全部客人的最小体力消耗之和。
输入格式
第一行两个整数 。
接下来 行,每行 个整数,给出矩阵 。随后 行,每行 个整数,给出矩阵 。
数据随机生成:每个 和 均独立、等概率从 到 中选取。如果 ,则交换两者。
输出格式
输出最小的总消耗。如果无解,输出 no solution。
样例输入 1
2 4
0 1 1 0
1 0 1 0
0 1 1 0
1 0 1 0
样例输出 1
10
第 桌的 号和第 桌的 号客人必须留在原桌,其他人需要换桌。一个最优方案是让两桌的 号座位客人互换,再让第 桌 号和第 桌 号客人互换,其余人留在原座位。
样例输入 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、2 | |
| 3–8 | |
| 9–14 | |
| 15–20 |