poj 1838

题意：有一只猴子喜欢吃香蕉，但他只能在相邻的两棵香蕉树之间行动，如果两棵树是在横方向或竖方向相邻的，那么这就组成一个区域，这个区域内猴子可以随意走动，有人可以把k个区域连接起来，从而使猴子在这k个区域内随意行动，问猴子最多可以在多少棵树内走动？给定n个树的坐标，和k。

思路：由于是区域相连接，所以可以想到用并查集这个数据结构进行操作。使用并查集来对这n个点进行操作，最后选出前k个最大的根节点相加即可。里面主要涉及到排序的问题，我这里采取的一致是STL算法模板中提供的qsort算法，下面关于qsort算法有一点小小的感受。int cmp(const void *a,const void *b)；（红色字体是其固定模式，必须这样写，黑色的则是自己随便起的名字）（其函数体详见后面），并且规定这个函数只能返回int型值。以前没有注意到这个问题，就随便操作，导致很多问题出现。

下面提供代码：

#include <iostream>
using namespace std;


struct point
{
	int x,y;
	int index;
}data[16020];

int father[16020];
int rank[16020];
int sum[16020];
int mem[16020];

int cmp(const void *a,const void *b)
{
	return *(int *)b-*(int *)a;
}

int cmp1(const void *p1,const void *p2)//对point 先x后y排序
{
	if((*((point*)p1)).x==(*((point*)p2)).x)
	{
		return (*((point*)p1)).y-(*((point*)p2)).y;
	}
	return (*((point*)p1)).x-(*((point*)p2)).x;
}
int cmp2(const void *a,const void *b)//先对y再对x排序
{
	if(((point *)a)->y!=((point *)b)->y)
		return ((point *)a)->y-((point *)b)->y;
	return ((point *)a)->x-((point *)b)->x;
}


void make_set(int x)
{
	father[x]=x;
	rank[x]=0;
	sum[x]=1;
}
int find_set(int x)
{
	if (father[x]!=x)
		father[x]=find_set(father[x]);
	return father[x];
}

void Union_set(int x,int y)
{
	int rootx=find_set(x);
	 	int rooty=find_set(y);
 	if(rootx==rooty)//在一棵树上
	 		return;
		
 	if(rank[rootx]<rank[rooty])//y所在树高，所以挂到x的根上   
	 	{
	 		father[rootx]=rooty;
	 		sum[rooty]+=sum[rootx];//!!!!!!!!!之前有错误原因在于写作了sum[x]+=sum[y];!!!!!!!!
	 	}
	 	else if(rank[rootx]>rank[rooty]) //根据rank是为了得到更低的树     !!!!!!!!之前有错误写作if(rank[y]>rank[x])反了两次!!!!!
	 	{
	 		father[rooty]=rootx;
	 		sum[rootx]+=sum[rooty];//!!!!!之前一直WA原因是写成sum[y]+=sum[x]!!!!!!所以注意这里所有的都是用的rootx，rooty
	 		
	 	}
		else
	 	{
	 		rank[y]++;
	 		father[rootx]=rooty;
	 		sum[rooty]+=sum[rootx];
	 	}


}

int main()
{
	int n,k;
	cin>>n>>k;
	int i;
	for (i=0;i<n;i++)
	{
		cin>>data[i].x>>data[i].y;
		data[i].index=i;
		make_set(data[i].index);
	}
	qsort(data,n,sizeof(point),cmp1);
	for (i=0;i<n-1;i++)
	{
		if ((data[i].x==data[i+1].x)&&(data[i+1].y-data[i].y==1))
			Union_set(data[i].index,data[i+1].index);
	}
	qsort(data,n,sizeof(point),cmp2);
	for (i=0;i<n-1;i++)
	{
		if ((data[i].y==data[i+1].y)&&(data[i+1].x-data[i].x==1))
			Union_set(data[i].index,data[i+1].index);
	}
	int begin=0;
	for (i=0;i<n;i++)
	{
		if(father[i]==i)
			mem[begin++]=sum[i];
	}
	int ans=0;
	qsort(mem,begin,sizeof(int),cmp);
	for (i=0;i<k;i++)
		ans+=mem[i];
	cout<<ans<<endl;
	return 0;

}

 

<!--EndFragment-->