live archive 4846 Mines

Mines
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=382&problem=2847&mosmsg=Submission+received+with+ID+842829

問題概要

それぞれの爆弾について、位置と誘爆する範囲が与えられる。
全部の爆弾を爆発させる最小の手数を求めよ。

解法

強連結成分分解をして、エッジが自分に伸びてない連結成分を数える。

ソース

#include<iostream>
#include<vector>
#include<cmath>
#include<cstdlib>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;

const int MAX_V = 3000;

int V;
vector<int> G[MAX_V], rG[MAX_V], vs;
bool used[MAX_V];
int cmp[MAX_V];

void init(){
  rep(i, MAX_V){
    G[i].clear();
    rG[i].clear();
  }
  vs.clear();
}

void add_edge(int from, int to){
  G[from].push_back(to);
  rG[to].push_back(from);
}

void dfs(int v){
  used[v] = true;
  rep(i, G[v].size()){
    if(!used[G[v][i]])dfs(G[v][i]);
  }
  vs.push_back(v);
}

void rdfs(int v, int k){
  used[v] = true;
  cmp[v] = k; 
  rep(i, rG[v].size()){
    if(!used[rG[v][i]])rdfs(rG[v][i], k);
  }
}

int scc(){
  rep(i, MAX_V)used[i] = false;
  vs.clear();
  rep(v, V){
    if(!used[v])dfs(v);
  }
  rep(i, MAX_V)used[i] = false;
  int k = 0;
  for(int i = vs.size() -1; i>=0;i--){
    if(!used[vs[i]])rdfs(vs[i], k++);
  }
  return k;
}

class Bomb{
public:
  int x, y, d;
};

bool isChain(Bomb a, Bomb b){
  int xDiff = abs(a.x - b.x);
  int yDiff = abs(a.y - b.y);
  return (max(xDiff, yDiff) <= a.d/2);
}

int main(){
  int T;
  cin >> T;
  rep(tc, T){
    init();
    cin >> V;
    vector<Bomb> B(V);
    rep(i, V){
      cin >> B[i].x >> B[i].y >> B[i].d;
    }
    rep(i, V){
      rep(j, V){
        if(isChain(B[i], B[j]))add_edge(i, j);
      }
    }
    const int SC = scc();
    int S[SC];
    rep(i, SC)S[i] = -1;;
    rep(i, V){
      FOR(it, G[i]){
        if(cmp[i] == cmp[*it])continue;
        S[cmp[*it]]++;
      }
    }
    int ans = 0;
    rep(i, SC){
      if(S[i] == -1)ans++;
    }
    cout << ans << endl;
  }
  return 0;
}