A – Wireless Network – 老虫儿的笔记本

An earthquake takes place in Southeast Asia. The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computers, but an unexpected aftershock attacked, all computers in the network were all broken. The computers are repaired one by one, and the network gradually began to work again. Because of the hardware restricts, each computer can only directly communicate with the computers that are not farther than d meters from it. But every computer can be regarded as the intermediary of the communication between two other computers, that is to say computer A and computer B can communicate if computer A and computer B can communicate directly or there is a computer C that can communicate with both A and B.

In the process of repairing the network, workers can take two kinds of operations at every moment, repairing a computer, or testing if two computers can communicate. Your job is to answer all the testing operations.

Input

The first line contains two integers N and d (1 <= N <= 1001, 0 <= d <= 20000). Here N is the number of computers, which are numbered from 1 to N, and D is the maximum distance two computers can communicate directly. In the next N lines, each contains two integers xi, yi (0 <= xi, yi <= 10000), which is the coordinate of N computers. From the (N+1)-th line to the end of input, there are operations, which are carried out one by one. Each line contains an operation in one of following two formats:
1. “O p” (1 <= p <= N), which means repairing computer p.
2. “S p q” (1 <= p, q <= N), which means testing whether computer p and q can communicate.

The input will not exceed 300000 lines.

Output

For each Testing operation, print “SUCCESS” if the two computers can communicate, or “FAIL” if not.

Sample Input

Sample Output

FAIL
SUCCESS

题意：给一些坏的点，给一个限制距离，只有两台机器都完好并且距离小于m的时候（距离可以限制是对于每条路径上相邻点的限制，并非对询问的终点与起点的直接限制），输出s,否则输出f
题解：一开始想的是，每次加入好的点时，去和前面所有点进行并查，但这样复杂度就是O（n^3），但实际上，由于前面的都已经连接过了，只需要在新加好的机器的时候判断是否符合距离限制，然后选择是否加入即可。
代码：

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

const int maxn = 1e3+5;

int repair[maxn];
int pre[maxn];
struct cor{
	int x;
	int y;
	cor(int _x=0,int _y=0):x(_x),y(_y){}
}co[maxn];

int find(int x){
	return pre[x]==x?x:pre[x]=find(pre[x]);
}
//int find(int x)
//{
//    if(pre[x] != x) pre[x] = find(pre[x]);
//    return pre[x];
//}

int dist(cor &a, cor &b){
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

void unionn(int a,int b){
	a = find(a);
	b = find(b);
	if(a != b) pre[a]=b; 
}


int main(){
	int n,m;
	scanf("%d%d", &n,&m);
	CLR(repair);
	rep(i,1,n){
		pre[i] = i;
		scanf("%d%d", &co[i].x,&co[i].y);
	}
	string t;
	int cnt=0;
	while(cin>>t)
	{
		int a,b;
		if(t[0]=='O'){
			scanf("%d", &a);
			for(int i = 1; i <= cnt;i++){
				if(dist(co[a],co[repair[i]])<=m*m) {
					unionn(a,repair[i]);
				}
			}
				
					
			repair[++cnt] = a;
		}else{
			scanf("%d%d",&a,&b);
			a = find(a);
			b = find(b);
			if(a == b)cout<<"SUCCESS"<<endl;
			else cout<<"FAIL"<<endl;
		}
	}
	return 0;
}

另外，并查集可以根据层数来优化

/**
2015 - 09 - 18 晚上
Author: ITAK
Motto:
今日的我要超越昨日的我，明日的我要胜过今日的我，
以创作出更好的代码为目标，不断地超越自己。
**/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
typedef long long LL;
const int maxn = 1005;
const double eps = 1e-7;
 
struct node
{
    int x, y;
} arr[maxn];
 
int rank[maxn], fa[maxn], num[maxn];
///基本上是模板
void Init(int x)
{
    for(int i=1; i<=x; i++)
    {
        fa[i] = i;
        rank[i] = 0;
    }
}
 
int Find(int x)
{
    if(fa[x] != x)
        fa[x] = Find(fa[x]);
    return fa[x];
}
 
void Union(int x, int y)
{
    int fx = Find(x), fy = Find(y);
    if(fx == fy)
        return;
    if(rank[fx] > rank[fy])
        fa[fy] = fx;
    else
    {
        fa[fx] = fy;
        if(rank[fx] == rank[fy])
            rank[fy]++;
    }
}
///计算距离（x 与 y）
int Dis(node A, node B)
{
    return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y);
}
char str[20];
 
int main()
{
    int m, d, xx, yy;
    scanf("%d%d",&m, &d);
    Init(m);
    for(int i=1; i<=m; i++)
        scanf("%d%d",&arr[i].x, &arr[i].y);
    int cnt = 0;
    while(cin>>str)
    {
        if(str[0] == 'O')
        {
            cin>>xx;
            for(int i=0; i<cnt; i++)
                ///每次判断是不是需要联合起来
                if(Dis(arr[num[i]], arr[xx]) <= d*d)
                    Union(num[i], xx);
            num[cnt++] = xx;
        }
        else if(str[0] == 'S')
        {
            cin>>xx>>yy;
            int fx = Find(xx);
            int fy = Find(yy);
            if(fx == fy)
                puts("SUCCESS");
            else
                puts("FAIL");
        }
    }
    return 0;
}

发表评论 取消回复

发表评论取消回复