学步园

有一个M行N列的点阵，相邻两点可以相连。一条纵向的连线花费一个单位，一条横向的连线花费两个单位。某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。

【输入数据】

    第一行输入两个正整数m和n。

    以下若干行每行四个正整数x1,y1,x2,y2，表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1-x2|+|y1-y2|=1。

【输出数据】

    输出使得连通所有点还需要的最小花费。

【输入样例】

2 2

1 1 2 1

【输出样例】

3

时间限制

    各测试点1秒

内存限制

你的程序将被分配32MB的运行空间

题解和数据  密码：bjp5

本题是一个最小生成树和并查集的结合体，具体思想看代码及注解

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int m,n,tot=0,f[1000001];//此题关键是如何把二维转换成一维，这样才能用并茶几 
void init();//m*n的矩阵转成一维数组，共有m*n个元素，第i行j列的元素转成一维后 
int find(int);//对应于一位下标为(i-1)*n+j，n表示矩阵共多少列 
void merge(int,int);
void work();
int main()
{
	init();
	work();
	return 0;
}
void init()
{
	cin>>m>>n;
	for(int i=1;i<=m*n;i++)f[i]=i;//并查集初始化 
	while(!cin.eof())//当未到文件结束 
	{
		int x,y,x1,x2,y1,y2;
		cin>>x1>>y1>>x2>>y2;
		x=(x1-1)*n+y1;//把(x1,y1)转到一维 
		y=(x2-1)*n+y2;
		merge(x,y);//合并 
	}
}
void work()
{
	int x,y;
	for(int i=1;i<=n;i++)//先枚举每一条纵边，每列有m条纵边 
	  for(int j=1;j<=m-1;j++)//枚举每条纵边的起始端点 
	  {
	  	  x=(j-1)*n+i;//纵边的上端点 
	  	  y=j*n+i;//纵边的下端点 
	  	  x=find(x);
	  	  y=find(y);
	  	  if(x!=y)//如果两端点不在一个集合则总数+1，并合并 
	  	  {
	  		  tot++;
	  		  merge(x,y);
	  	  }
	  }
	for(int i=1;i<=m;i++)//枚举每条横边 
	{
		for(int j=1;j<=n-1;j++)
		{
			x=(i-1)*n+j;//衡边的左端点 
			y=x+1;//右端点等于左端点+1 
			x=find(x);
			y=find(y);
			if(x!=y)//不在一个集合则总数+2，并合并 
			{
				tot+=2;
				merge(x,y);
			}
		}
	}
	cout<<tot<<endl;
}
int find(int x)
{
	if(f[x]==x)return x;
	f[x]=find(f[x]);
	return f[x];
}
void merge(int x,int y)
{
	x=find(x);
	y=find(y);
	f[y]=x;
}