Gym - 100783F City Park（并查集的运用）

题目链接：点击打开链接

题目大意：给出一些矩阵，如果矩阵之间有接触算作一个连通分量，问最大的连通分量的面积为多少？

思路：既然接触即算为一个连通分量，那么我们可以分别讨论他的横边接触和竖边接触。

将横边和竖边分别存储在不同的结构体数组中，然后对数组进行排序，将互相接触的边对应的矩阵放在统一并查集中。

最后统计下所有并查集的面积大小，输出最大的一个即可。

#include<iostream>
#include<cstdio>
#include<cstring >
#include <cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=50000+10;
#define inf 0x3f3f3f3f
int pre[maxn<<1],sum[maxn<<1];
int fid(int x)
{
	if(pre[x]==x)return x;
	return pre[x]=fid(pre[x]);
}
void join(int x,int y)
{
	int fx=fid(x),fy=fid(y);
	if(fx!=fy)
	{
		pre[fx]=fy;
	}
}
struct node
{
	int x,y,w,h;
}nodes[maxn];
struct line
{
	int x,l,r,pos;
	bool operator <(const line&tmp)const
	{
		return (x<tmp.x||x==tmp.x&&l<tmp.l||x==tmp.x&&l==tmp.l&&r<tmp.r);
	}
}a[maxn<<1],b[maxn<<1];//一个水平 一个垂直
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		for(int i=1;i<=n;i++)pre[i]=i;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d%d%d",&nodes[i].x,&nodes[i].y,&nodes[i].w,&nodes[i].h);
			//水平线段
			a[i].x=nodes[i].y,a[i].l=nodes[i].x,a[i].r=nodes[i].x+nodes[i].w,a[i].pos=i;
			a[i+n].x=nodes[i].y+nodes[i].h,a[i+n].l=nodes[i].x,a[i+n].r=nodes[i].x+nodes[i].w,a[i+n].pos=i;

			//垂直线段
			b[i].x=nodes[i].x,b[i].l=nodes[i].y,b[i].r=nodes[i].y+nodes[i].h,b[i].pos=i;
			b[i+n].x=nodes[i].x+nodes[i].w,b[i+n].l=nodes[i].y,b[i+n].r=nodes[i].y+nodes[i].h,b[i+n].pos=i;

		}
		sort(&a[1],&a[1]+2*n);
		sort(&b[1],&b[1]+2*n);
		/*for(int i=1;i<=2*n;i++)
			printf("%d %d %d\n",a[i].x,a[i].l,a[i].r);*/
		int m=2*n;
		memset(sum,0,sizeof sum);
		for(int i=1,j;i<=m;)
		{
			int tx=a[i].r;
			j=i+1;
			while(j<=m&&a[j].x==a[i].x&&a[j].l<=tx)
			{
				tx=max(tx,a[j].r);
				join(a[i].pos,a[j].pos);
				j++;
			}
			i=j;
		}
		for(int i=1,j;i<=m;)
		{
			int tx=b[i].r;
			j=i+1;
			while(j<=m&&b[j].x==b[i].x&&b[j].l<=tx)
			{
				tx=max(tx,b[j].r);
				join(b[i].pos,b[j].pos);
				j++;
			}
			i=j;
		}
		for(int i=1;i<=n;i++)
		{
			sum[fid(i)]+=nodes[i].h*nodes[i].w;
			//cout<<sum[fid(i)]<<endl;
		}
		int ans=0;
		for(int i=1;i<=n;i++)
			ans=max(ans,sum[i]);
		printf("%d\n",ans);
	}
	return 0;
}