向往的气球
时间： 1ms 内存：128M
描述：
一年一度的计控ACM院赛即将来临。除了ACMers以外，志愿者们也非常的忙碌。他们需要将各种颜色的气球分配给A掉相应题目的队伍。现在，所有比赛队伍的成员都处在一个房间中，这个房间是一个二维坐标系，大小为1000行x1000列。
每一个坐标对应着空座位或某个参赛队伍。每一分钟，志愿者们都应该把所有的气球聚集在一起。志愿者将会被告知把气球送到哪里。为了保证工作的效率，对于两个坐标(x1,y1)和(x2,y2)，如果|x1-x2|不大于k 或者 |y1-y2|不大于k，则这两个坐标的气球由同一个志愿者配送。你能知道最少需要多少志愿者，才能配送完所有的气球吗？
输入：
第一行包含一个整数T，表示有T组数据。
对于每一组数组，这里将有n+1行
第一行：输入两个整数n,k; n表示气球的数量，k表示题目中的k值
接下来的n行中，每一行包含两个整数r,c。表示气球应该被送往r行，c列。请注意坐标可能会相同。
题目中保证：T<=100,1<=n<=10000,1<=k,r,c<=1000
输出：
对于每一组数据，你需要输出一行
输出最少需要的志愿者数量
示例输入：
2
3 5
1 1
10 6
15 20
2 5
1 1
7 7示例输出：
1
2提示：
参考答案（内存最优[1276]）：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e4+5;
int n,m,f[maxn];
struct node {
int x,y,idx;
} a[maxn];
bool cmp1(node a,node b) { return a.x<b.x; }
bool cmp2(node a,node b) { return a.y<b.y; }
int Find(int x)
{
if(f[x]==x)
return x;
else
{
f[x]=Find(f[x]);
return f[x];
}
// return f[x]==x?x:f[x]=Find(f[x]);
}
void Union(int x,int y) {
x=Find(a[x].idx),
y=Find(a[y].idx);
if(x!=y)
f[y]=x;
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
// memset(f,-1,sizeof f);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=n;i++) {
scanf("%d%d",&a[i].x,&a[i].y);
a[i].idx=i;
}
sort(a+1,a+n+1,cmp1);
for(int i=1;i<n;i++)
if(a[i+1].x-a[i].x<=m)
Union(i+1,i);
sort(a+1,a+1+n,cmp2);
for(int i=1;i<n;i++)
if(a[i+1].y-a[i].y<=m)
Union(i+1,i);
int ans = 0;
for(int i=1;i<=n;i++)
if(f[a[i].idx]==a[i].idx)
ans++;
printf("%d\n",ans);
}
return 0;
}
参考答案（时间最优[11]）：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e4+5;
int n,m,f[maxn];
struct node {
int x,y,idx;
} a[maxn];
bool cmp1(node a,node b) { return a.x<b.x; }
bool cmp2(node a,node b) { return a.y<b.y; }
int Find(int x)
{
if(f[x]==x)
return x;
else
{
f[x]=Find(f[x]);
return f[x];
}
// return f[x]==x?x:f[x]=Find(f[x]);
}
void Union(int x,int y) {
x=Find(a[x].idx),
y=Find(a[y].idx);
if(x!=y)
f[y]=x;
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
// memset(f,-1,sizeof f);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=n;i++) {
scanf("%d%d",&a[i].x,&a[i].y);
a[i].idx=i;
}
sort(a+1,a+n+1,cmp1);
for(int i=1;i<n;i++)
if(a[i+1].x-a[i].x<=m)
Union(i+1,i);
sort(a+1,a+1+n,cmp2);
for(int i=1;i<n;i++)
if(a[i+1].y-a[i].y<=m)
Union(i+1,i);
int ans = 0;
for(int i=1;i<=n;i++)
if(f[a[i].idx]==a[i].idx)
ans++;
printf("%d\n",ans);
}
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。