当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
6564：Wheel of Fortune
题目描述
The Wheel of Fortune reminds you that the wheel is always turning and life is in a state of constant change. If you’re going through a difficult time right now, rest assured it can only get better from here and soon you will be blessed with good luck and good fortune. Similarly, if things are going amazingly well, know that this too will change and life may return to ’normal’ soon after. This is why it is so important to cherish the blissful moments in your life and make the most of them while they are within reach – because in a flash they could be gone.
Alice wants to make a wheel and decorate it with a circle of jewels. She has $n$ different jewels each of which can be colored in $m$ colors. The arrangement of Jewels always symbolizes fortune. Specifically, when the $i$-th jewel is colored with the $c_i$-th color, it is attached with $a_i$,$c_i$ amount of luck. After coloring all the $n$ jewels, she needs to arrange them in some order $k_1$, $k_2$, · · · , $k_n$(a permutation) such that no two adjacent jewels on the wheel are of the same color. Otherwise she may encounter disasters. Alice enjoys peaceful life and wants to find the minimum possible |max{$a_{k_i}$,$c_{k_i}$|1 ≤ $i$ ≤ $n$} - min{$a_{k_i}$,$c_{k_i}$|1 ≤ $i$ ≤ $n$}from all the valid arrangements.
Alice wants to make a wheel and decorate it with a circle of jewels. She has $n$ different jewels each of which can be colored in $m$ colors. The arrangement of Jewels always symbolizes fortune. Specifically, when the $i$-th jewel is colored with the $c_i$-th color, it is attached with $a_i$,$c_i$ amount of luck. After coloring all the $n$ jewels, she needs to arrange them in some order $k_1$, $k_2$, · · · , $k_n$(a permutation) such that no two adjacent jewels on the wheel are of the same color. Otherwise she may encounter disasters. Alice enjoys peaceful life and wants to find the minimum possible |max{$a_{k_i}$,$c_{k_i}$|1 ≤ $i$ ≤ $n$} - min{$a_{k_i}$,$c_{k_i}$|1 ≤ $i$ ≤ $n$}from all the valid arrangements.
输入解释
The input starts with a line containing a number $T$ which indicates the number of test cases. Each test case starts with a line containing two numbers $n$ (2 ≤ $n$ ≤ 2000) and $m$ (1 ≤ $m$ ≤ 2000) which indicate the number of jewels and colors respectively. Then n lines follow and each contains m numbers indicating $a_{i,j}$ (1 ≤ $a_{i,j}$ ≤ 1000000)
输出解释
For each test case, please print only one line in the form of “Case $x$: $ans$”, where $x$ is the test number and $ans$ indicates the answer. If it is impossible for Alice to find a valid arrangement, the answer is -1.
输入样例
2 4 2 1 2 2 1 1 1 2 2 4 3 8 3 7 2 6 7 2 7 3 5 6 3
输出样例
Case 1: 1 Case 2: 1
提示
The following picture is the illustration of the samples, in which numbers and shapes indicate indexes of jewels and their colors separately. In the first sample, we use the first color to color the jewels with indexes 1 and 3, and color the others with the second color. In the second sample, we use the second color to color the jewel with index 1, the first color to color the jewels with indexes 2 and 3, and the third one to color the jewel with index 4. The orders of jewels are illustrated below.
来自杭电HDUOJ的附加信息
| Recommend | chendu |
最后修改于 2020-10-25T23:32:22+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
| 时间上限 | 内存上限 |
| 12000/8000MS(Java/Others) | 262144/262144K(Java/Others) |
登陆或注册以提交代码