一道简单题,但是很有意思,简单写一下。
题目大意是,有M种卡片,每种有N个,初始时放在M个盒子里,每个盒子里有N张,但是可能有某些卡片放错了位置,因此需要进行一些移动,最后使得每张卡片都放到它应该在的盒子(第1种卡片都放入盒子1,第2种卡片都放入盒子2……)。一次移动是指把一张卡片从当前手边的盒子里拿出放到另一个盒子,或者不拿卡片,只是把手从当前的盒子处移到另一个盒子处。
容易联想到欧拉路,如果盒子i里面有一张卡片j,就把i,j之间连一条边,表示至少要有一次从i到j的移动。容易发现这样建图后每个点的出度必然等于入度(因为初始时盒子里就有N张卡片,后面拿出多少张也就要拿入多少张),也就是说对于每个连通分量,欧拉回路必定存在,最少的移动次数实际上就是边的总数。在不同的连通分量之间必然要有一次空着手的移动。因此最后的答案就是 边数+连通分量数-1(第一次开始时手可以在任何位置)。


