并查集 - UVALive 6889 City Park

By | 08月10日
Advertisement

City Park

Problem's Link: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=129725


Mean:

在网格中给你一些矩形,求最大连通块的面积。

analyse:

由于题目保证了矩形不会相交,所以不用扫描线也可做。

先把所有的线段分为横向和纵向,然后排序,依次判断是否相邻,相邻就用并查集合并,最后再用并查集统计一下面积,取最大值即可。

Time complexity: O(N)

Source code:

/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-09-16.10
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

void scan(int &x)
{
x=0;
char c=getchar();
while(!(c>='0' && c<='9' || c=='-')) { c=getchar(); }
bool flag=1;
if(c=='-')
{
flag=0; c=getchar();
}
while(c>='0' && c<='9')
{
x=x*10+c-'0'; c=getchar();
}
if(!flag) { x=-x; }
}
void scan2(int &x,int &y) { scan(x),scan(y);}
void scan3(int &x,int &y,int &z) { scan(x),scan(y),scan(z); }
/**************************************END define***************************************/
const int MAXN=50010;
int n,x,y,w,h,f[MAXN],area[MAXN],answer[MAXN];
struct L {
int x,l,r,id;
L(int a,int b,int c,int d) : x(a), l(b), r(c), id(d) {}
bool operator <(const L &a) const { return x==a.x? l<a.l:x<a.x;}
};
vector<L> L1,L2;
int Find(int x) { return f[x]==x?x:f[x]=Find(f[x]); }

void work(int si,vector<L> &LL) {
int a,b,j=1;
for(int i=0; i<si; i=j,++j) {
while(j<si && LL[j].x == LL[i].x) ++j;
int li = LL[i].r,id=LL[i].id;
for(int k=i+1; k<j; ++k) {
if(LL[k].l<=li) {
a=Find(id),b=Find(LL[k].id);
if(a!=b) f[a]=b;
}
if(LL[k].r>li) li=LL[k].r,id=LL[k].id;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
while(~scanf("%d",&n))
{
L1.clear(),L2.clear();
for(int i=0; i<n; ++i)
{
scan2(x,y),scan2(w,h);
L1.push_back(L(x,y,y+h,i));
L1.push_back(L(x+w,y,y+h,i));
L2.push_back(L(y,x,x+w,i));
L2.push_back(L(y+h,x,x+w,i));
f[i]=i,area[i]=w*h,answer[i]=0;
}
sort(L1.begin(),L1.end());
sort(L2.begin(),L2.end());
work(L1.size(),L1);
work(L2.size(),L2);
int ans=INT_MIN;
for(int i=0; i<n; ++i) { answer[Find(i)]+=area[i]; }
for(int i=0; i<n; ++i) ans=max(ans,answer[i]);
cout<<ans<<endl;
}
return 0;
}
/*

*/

Similar Posts:

  • UVALive 4730 Kingdom(并查集加 线段树或树状数组)

    题意:有T组测试数据,每组数据的N表示有N个城市,接下来的N行里每行给出每个城市的坐标(0<=x,y<=1000000),然后有M(1<M<200000)个操作,操作有两类,(1)"road A B",表示将城市A和城市B通过一条道路连接,如果A和B原来属于不同的城市群,经过这个操作,A和B就在一个城市群里了,保证每条道路不会和其他道路相交(除了端点A和B).(2)"line C",表示查询当穿过y=C的直线,有多少个城市群.这几个城市群一共

  • UVALive 4730 Kingdom 线段树+并查集

    题目链接:点击打开链接 题意见白书P248 思路: 先把读入的y值都扩大2倍变成整数 然后离散化一下 用线段树来维护y轴 区间上每个点的 城市数量和联通块数量, 然后用并查集维护每个联通块及联通块的最大最小y值,还要加并查集的秩来记录每个联通块的点数 然后就是模拟搞.. T^T绝杀失败题..似乎数组开小了一点就过了,== #include<stdio.h> #include<math.h> #include<vector> #include<string.h>

  • UVALive - 3644 - X-Plosives (并查集!!)

    X-Plosives A secret service developed a new kind of explosive that attain its volatile property only when a specific association of products occurs. Each product is a mix of two different simple compounds, to which we call a binding pair. If N>2, the

  • 暑假训练(UVALive 5789-5799)(线段树+并查集+dp+桥)

    A :http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83308#problem/A 题意:将区间(l,r)的人杀掉,并且输出左边和右边第一个没死的人 思路:线段树,或者并查集 #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<vector> #include<cmath&

  • [置顶] 杭电3635-Dragon Balls-并查集之路径压缩

    Problem Description Five hundred years later, the number of dragon balls will increase unexpectedly, so it's too difficult for Monkey King(WuKong) to gather all of the dragon balls together. His country has N cities and there are exactly N dragon bal

  • hdu 3635 Dragon Balls(并查集)

    Dragon Balls Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2909 Accepted Submission(s): 1125 Problem Description Five hundred years later, the number of dragon balls will increase unexpectedly,

  • poj 1703 Find them, Catch them(并查集)

    Description The police office in Tadu City decides to say ends to the chaos, as launch actions to root up the TWO gangs in the city, Gang Dragon and Gang Snake. However, the police first needs to identify which gang a criminal belongs to. The present

  • hdu 5441 并查集

    Travel Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 2331 Accepted Submission(s): 804 Problem Description Jack likes to travel around the world, but he doesn't like to wait. Now, he is traveli

  • Gym 100712F Travelling Salesman(二分+并查集)

    /********* Gym 100712F Travelling Salesman After leaving Yemen, Bahosain now works as a salesman in Jordan. He spends most of his time travelling between different cities. He decided to buy a new car to help him in his job, but he has to decide about

  • Find them, Catch them(POJ 1703 关系并查集)

    Find them, Catch them Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 38668 Accepted: 11905 Description The police office in Tadu City decides to say ends to the chaos, as launch actions to root up the TWO gangs in the city, Gang Dragon an

Tags: