Mosaic

Time limit: 0.25 second
Memory limit: 64 MB
There's
no doubt that one of the most important and crucial things to do in
this world is to bring up children. May be, if you study properly and
reach good results at the competition you'll get a position of nanny in a
kindergarten. But you are to get ready for it! Let's consider some
problems that a nanny has to solve in a kindergarten.
Everyone knows the game "Mosaic". Playing the game, one is to lay out pictures of different colored pieces. Let there be M different boxes and N mosaic pieces of each of the M
colors. After playing the game children rarely put the pieces back to
their boxes correctly so that the color of the box and the colors of its
pirces would be the same. A nanny has to do that.
Children have already put the mosaic pieces to the boxes but possibly not correctly. There are N
pieces in each box. Some pieces (possibly all of them) are located in
wrong boxes (i.e. boxes with pieces of a different color). Moving a hand
once one can take a piece from one box to another or simply move the
hand to another box. You may start from any box you like. The movement
towards the first box is not taken into account. Find out the minimal
number of movements one needs to put all the mosaic pieces to their
boxes.

Input

The first line contains integers 2 ≤ M ≤ 500 (the number of colors) and 2 ≤ N ≤ 50 (the number of pieces of each color), Each of the next M lines contains N numbers in the range from 1 to M (the i+1-st line contains colors of pieces located in the i-th box). The numbers are separated with a space.

Output

the minimal possible number of hand movements that one has to make in order to take all the pieces to their boxes.

Sample

input output
4 3
1 3 1
2 3 3
1 2 2
4 4 4
6
Problem Author: Stanislav Vasilyev
【题意】有M种卡片,每种有N个,初始时放在M个盒子里,每个盒子里有N张,但是可能有某些卡片放错了位置,因此需要进行一些

移动,最后使得每张卡片都放到它应该在的盒子(第1种卡片都放入盒子1,第2种卡片都放入盒子2……)。一次移动是指把一张卡片从

当前手边的盒子里拿出放到另一个盒子,或者不拿卡片,只是把手从当前的盒子处移到另一个盒子处。

【分析】容易联想到欧拉路,如果盒子i里面有一张卡片j,就把i,j之间连一条边,表示至少要有一次从i到j的移动。容易发现这样建图后每个点

的出度必然等于入度(因为初始时盒子里就有N张卡片,后面拿出多少张也就要拿入多少张),也就是说对于每个连通分量,欧拉回路必

定存在,最少的移动次数实际上就是边的总数。在不同的连通分量之间必然要有一次空着手的移动。因此最后的答案就是 边数+连通分

量数-1(第一次开始时手可以在任何位置)。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
typedef long long ll;
using namespace std;
const int N = +;
const int M = +;
const int mod=1e9+;
int n,m,k,t;
int vis[N];
int s[N];
int parent[N];
int Find(int x)
{
if(parent[x]!=x)parent[x]=Find(parent[x]);
return parent[x];
}
void Union(int x,int y)
{
x=Find(x);y=Find(y);
if(x==y)return;
parent[y]=x;
}
int main()
{
int u,v,ans=;
for(int i=;i<N;i++)parent[i]=i;
scanf("%d%d",&m,&n);
for(int i=;i<=m;i++){
for(int j=;j<=n;j++){
scanf("%d",&u);
if(i!=u){
vis[i]=vis[u]=;
ans++;
Union(i,u);
}
}
}
for(int i=;i<=m;i++){
if(vis[i]&&!s[Find(i)]){
ans++;
s[Find(i)]=;
}
}
printf("%d\n",ans==?:ans-);
return ;
}

最新文章

  1. Maven-004-使用 Nexus 搭建 maven 私服
  2. NHibernate系列文章十:NHibernate对象二级缓存下
  3. array,vertor,arraylist,hashable,hashmap等几个易混淆概念的区别
  4. 动态链接库找不到 : error while loading shared libraries: libgsl.so.0: cannot open shared object file: No such file or directory
  5. 将decimal类型的数值后面的0和.号去掉
  6. java文件上传--基于ajaxFileUpload+struts2
  7. 通过qsort(void * lineptr[], int left, int rifht, int (*comp)(void *, void *))解读指针函数和void指针
  8. Android View的事件分发
  9. less中的变量
  10. SQLServer之修改数据库架构
  11. js生成[n,m]的随机数,js如何生成随机数,javascript随机数Math.random()
  12. java课程之团队开发冲刺1.5
  13. Android Studio 之 项目瘦身、代码检查
  14. Android 全屏设置和禁止横屏竖屏切换
  15. 题解-拉格朗日(bzoj3695变种)
  16. Nginx实战-后端应用健康检查
  17. sql server 压缩备份数据库
  18. linux下通过sed命令直接修改文件内容
  19. RabbitMQ的安装与管理控制台设置
  20. 元组(Tuple)

热门文章

  1. bzoj 2820 YY的GCD 莫比乌斯反演
  2. powershell小工具,efs加解密三剑客。
  3. Cisco IOS Debug Command Reference Command E through H
  4. 使用OCI向Oracle插入Geometry数据
  5. Mac下的SVN客户端工具Cornerstone使用教程
  6. sap 根据TOCE找 USER_EXIT
  7. js jquery 判断函数是否存在($.isFunction函数的使用)
  8. 练手CF3-C - Wormhouse
  9. 转载大神的dfs讲解
  10. 神奇彩带KMP