题目地址:http://poj.org/problem?id=2236

题目大意

东南亚发生一次地震把所有电脑都破坏了,现在需要依次修复以恢复无线网络。由于硬件限制每台电脑之间直连距离不能超过$D$。但是每台电脑都可以做相连两台电脑的中介,比如$A$和$B$都能和$C$连接,则$A$和$B$也能连通。

现在工程师只有两种操作,修电脑或者检查两台电脑是否连通,返回所有的检查结果。

思路

并查集无疑了。。首先将修好的电脑标记下,或者存储下,每次修电脑时检查是否能直连之前修过的电脑,能的话则连接(合并操作unite),然后测试的时候直接判断两台电脑是否连通(判断same)。

AC代码

/*************************************************************************
    > File Name: 2236.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-11-08 日 21:56:17 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int par[1024];
int N, D; // 电脑数量,距离
int dist[1024][1024];

struct computer {
    int x, y;
} comp[1024];


// bool repaired[1024];
int repaired[1024];

void init_union_found() {
    for(int i=1; i<=N; ++i) par[i] = i;
}
int find(int x) {
    return x==par[x]?x:par[x]=find(par[x]);
}

bool same(int x, int y) {
    return find(x) == find(y);
}
bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x!=y) par[x] = y;
    return true;
}

int d(int i, int j) {
    return dist[i][j] == -1?dist[i][j]=(comp[i].x-comp[j].x)*(comp[i].x-comp[j].x) + (comp[i].y-comp[j].y)*(comp[i].y-comp[j].y):dist[i][j];
}

void solve() {
    init_union_found();
    char op;
    int s, t;
    int cur, cnt=0;
    // cout << D << endl;
    // cout << d(1, 2) << endl;

    while(cin >> op) {
        if(op == 'S') {
            cin >> s >> t;
            // 判断是否连通
            if(same(s, t)) cout << "SUCCESS" << endl;
            else cout << "FAIL" << endl;
        }
        else {
            cin >> cur;
            // 和之前修过的电脑连接
            for(int i=0; i<cnt; ++i)
                d(repaired[i], cur) <= D && unite(repaired[i], cur); // cur和cnt容易写错。。
            repaired[cnt++] = cur;

            // for(int i=1; i<=N; ++i)
                // if(i!=cur && repaired[i] && d(i, cur) <= D)
                    // unite(i, cur);
            // repaired[cur] = true;
        }
    }

}

int main()
{
#ifdef Oj
    freopen("2236.in", "r", stdin);
#endif
    cin.sync_with_stdio(false); // 30万行数据
    cin >> N >> D;
    D*=D; // 这里之前写成D<<=1了。。。
    memset(dist, -1, sizeof(dist));
    for(int i=1;i<=N;++i)
        cin >> comp[i].x >> comp[i].y;

    solve();
    return 0;
}