题意：
给出许多个矩形，不重叠
问连通的矩阵块面积最大是多少
题解：
因为没有重叠的，所以我们可以分别对水平线和垂直线进行并查集合并
这里我犯了一个并查集的错误，就是在累加面积的时候写反了
void Unite(int num1,int num2) { int tx=find_it(num1); int ty=find_it(num2); if(tx!=ty){ father[tx]=ty; sum[ty]+=sum[tx]; } }上面写成了sum【tx】+=sum【ty】了导致错误这里还需注意的是，处理同一水平线上的线段要注意大小关系
两份代码，供参考
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define MAXN 100050 #define LL long long int father[MAXN]; LL sum[MAXN]; struct Point { int x,y; }; struct Line { Point p1,p2; int pos; }a[MAXN<<1],b[MAXN<<1]; int cmp1(Line A,Line B) { if(A.p1.y==B.p1.y) return A.p1.x < B.p1.x; return A.p1.y < B.p1.y; } int cmp2(Line A,Line B) { if(A.p1.x==B.p1.x) return A.p1.y < B.p1.y; return A.p1.x < B.p1.x; } int find_it(int x) { int tempx=x,t; while(tempx!=father[tempx]) tempx=father[tempx]; while(x!=father[x]) { t=father[x]; father[x]=tempx; x=t; } return tempx; } void Unite(int num1,int num2) { int tx=find_it(num1); int ty=find_it(num2); if(tx!=ty){ father[tx]=ty; sum[ty]+=sum[tx]; } } int main() { int n; //freopen("in.txt","r",stdin); while(scanf("%d",&n)!=EOF) { int x,y,w,h; memset(sum,0,sizeof(sum)); for(int i=0;i<n;i++){ scanf("%d%d%d%d",&x,&y,&w,&h); ///水平线段 a[i*2].p1.x=x , a[i*2].p1.y=y; a[i*2].p2.x=x+w, a[i*2].p2.y=y; a[i*2].pos=i; a[i*2+1].p1.x=x , a[i*2+1].p1.y=y+h; a[i*2+1].p2.x=x+w, a[i*2+1].p2.y=y+h; a[i*2+1].pos=i; ///垂直线段 b[i*2].p1.x=x , b[i*2].p1.y=y; b[i*2].pos=i; b[i*2].p2.x=x , b[i*2].p2.y=y+h; b[i*2+1].p1.x=x+w, b[i*2+1].p1.y=y; b[i*2+1].pos=i; b[i*2+1].p2.x=x+w, b[i*2+1].p2.y=y+h; sum[i]=w*h; } for(int i=0;i<=n;i++) father[i]=i; sort(a,a+n*2,cmp1); sort(b,b+n*2,cmp2); int last_x=a[0].p2.x,ty=a[0].p2.y; int last_y=b[0].p2.y,tx=b[0].p2.x; for(int i=1;i<n*2;i++){ if(a[i].p1.y==a[i-1].p1.y){ if(a[i].p1.y!=ty){ last_x=a[i-1].p2.x; ty=a[i].p1.y; } if(last_x>=a[i].p1.x) Unite(a[i-1].pos,a[i].pos); last_x=last_x>a[i].p2.x?last_x:a[i].p2.x; } if(b[i].p1.x==b[i-1].p1.x){ if(tx!=b[i].p1.x){ tx=b[i].p1.x; last_y=b[i-1].p2.y; } if(last_y>=b[i].p1.y) Unite(b[i-1].pos,b[i].pos); last_y=last_y>b[i].p2.y?last_y:b[i].p2.y; } } LL ans=0; for(int i=0;i<n;i++) ans=ans>sum[i]?ans:sum[i]; printf("%lld\n",ans); } return 0; }
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define MAXN 100050 #define LL long long int father[MAXN]; int sum[MAXN]; int W[MAXN],H[MAXN]; struct Line { int x,l,r,id; Line(int x=0,int l=0,int r=0,int id=0):x(x),l(l),r(r),id(id){} bool operator < (const Line &b)const{ return x<b.x||(x==b.x&&l<b.l)||(x==b.x&&l==b.l&&r<b.r); } }; Line a[MAXN*3],b[MAXN*3]; int find_it(int x) { if(father[x]!=x) father[x]=find_it(father[x]); return father[x]; } int main() { int n; //freopen("in.txt","r",stdin); while(scanf("%d",&n)!=EOF) { int x,y,w,h; memset(sum,0,sizeof(sum)); for(int i=0;i<n;i++){ scanf("%d%d%d%d",&x,&y,&w,&h); ///水平线段 a[i]=Line(y,x,x+w,i); a[i+n]=Line(y+h,x,x+w,i); ///垂直线段 b[i]=Line(x,y,y+h,i); b[i+n]=Line(x+w,y,y+h,i); W[i]=w; H[i]=h; father[i]=i; } int m=n<<1; sort(a,a+m); sort(b,b+m); for(int i=0;i<m;){ int j=i,mx=a[i].r; while(j<=m&&a[j].x==a[i].x) { if(a[j].l<=mx){ int tx=find_it(a[j].id); int ty=find_it(a[i].id); if(tx!=ty) father[tx]=ty; mx=max(mx,a[j].r); j++; } else break; } i=j; } for(int i=0;i<m;){ int j=i,mx=b[i].r; while(j<=m&&b[j].x==b[i].x) { if(b[j].l<=mx){ int tx=find_it(b[j].id); int ty=find_it(b[i].id); if(tx!=ty) father[tx]=ty; mx=max(mx,b[j].r); j++; } else break; } i=j; } int ans=0; int t; for(int i=0;i<n;i++){ t=find_it(i); sum[t]+=W[i]*H[i]; ans=max(ans,sum[t]); } printf("%d\n",ans); } return 0; }
