live archive 4846 Mines
問題概要
それぞれの爆弾について、位置と誘爆する範囲が与えられる。
全部の爆弾を爆発させる最小の手数を求めよ。
解法
強連結成分分解をして、エッジが自分に伸びてない連結成分を数える。
ソース
#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; }