B - Bomb HDU - 5934

Original link
The question ： A bomb has a blasting range , If a bomb explodes , All bombs in its range will also explode , The same is true of the detonated bomb , But detonating a bomb costs a certain price , Now give the location and explosion radius of some bombs , Ask the minimum cost of detonating all bombs .
Answer key ： I first thought of dp, Later, I thought of and searched the collection , Later, I found that it couldn't be solved A Can detonate B however ,B Not necessarily detonated A The problem of . Then I thought of strong connected components . Build a directed graph , He can solve the explosion in front , The latter must detonate , When we choose, we can only select the highest node , But the highest node is not necessarily only one , This uses strongly connected components , We can only select the node with the smallest weight in the connected component of the head node . And it should be noted here that you only need to choose the degree of penetration after the shrinkage point is 0 The connected component of , But there were some problems in the code writing during the training match , take id Record it bool There are various other details of this type , The following is the code for the training match ：（ It's wrong. ）

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
#define int long long
const int N = 1010;
const int M = 2e6 + 10;
int h[N], e[M], ne[M], idx, top;
bool id[N];// It's wrong here , Should be int
int timestamp;
int dfn[N], low[N], scc_cnt;
int Size[N];
int stk[N], w[N], n;
int iout[N];
int ans = 0;
struct node
{
    
  int x, y;
  int r, w;
} a[N];
void add(int a, int b)
{
    
  e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u)
{
    
  dfn[u] = low[u] = ++timestamp;
  stk[++top] = u, in_stk[u] = true;
  for (int i = h[u]; ~i; i = ne[i])
  {
    
    int j = e[i];
    if (!dfn[j])
    {
    
      tarjan(j);
      low[u] = min(low[j], low[u]);
    }
    else if (in_stk[u])// It's wrong here , Should be j
      low[u] = min(low[u], dfn[j]);
  }
  if (dfn[u] == low[u])
  {
    
    ++scc_cnt;
    int y;
    do
    {
    
      y = stk[top--];
      in_stk[y] = false;
      id[y] = scc_cnt;
      cout<<id[y]<<"--"<<scc_cnt<<"--"<<y<<endl;
      Size[scc_cnt]++;
      w[scc_cnt] = min(w[scc_cnt], a[y].w); //  The value of strongly connected components 
    } while (y != u);
  }
}
signed main()
{
    
  int t;
  scanf("%lld",&t);
  while (t--)
  {
    
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
      h[i] = -1;
    for (int i = 1; i <= n; i++)
      w[i] = 0x3f3f3f3f3f;
    for (int i = 1; i <= n; i++)
      in_stk[i] = false;
    for (int i = 1; i <= n; i++)
      iout[i] = 0;
    // Forget to initialize here low  and dfn 了 
    ans = 0;
    top = 0;
    idx = 0;
    scc_cnt = 0;
    for (int i = 1; i <= n; i++)
    {
    
      cin >> a[i].x >> a[i].y >> a[i].r >> a[i].w;
    }
    for (int i = 1; i <= n; i++)
    {
    
      for (int j = 1; j <= n; j++)
      {
    
        if(i==j) continue;
        int xx = (a[i].x - a[j].x) * (a[i].x - a[j].x);
        int yy = (a[i].y - a[j].y) * (a[i].y - a[j].y);
        if (xx + yy <= a[i].r * a[i].r) add(i, j);//printf("%lld %lld->\n",i,j);
      }
    }
    for (int i = 1; i <= n; i++)
    {
    
      if (!dfn[i]) tarjan(i);
    }
    printf("%lld--%lld\n",id[4],id[5]);
    for (int i = 1; i <= n; i++)
    {
    
      for (int j = h[i]; ~j; j = ne[j])
      {
    
        int k = e[j];
        int x = id[k];
        int y = id[i];
        if (x != y) iout[x]++;
        printf("%lld-->%lld",x,y);
      }
    }
    for (int i = 1; i <= scc_cnt; i++)
    {
    
      if (iout[i] == 0) ans += w[i];
    }
    printf("%lld\n", ans);
  }
  return 0;
}

Here is AC Code ：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
#define int long long
const int N = 1010;
const int M = 2e6 + 10;
int h[N], e[M], ne[M], idx, top;
int id[N];
int timestamp;
int dfn[N], low[N], scc_cnt;
int Size[N];
int stk[N], w[N], n;
bool in_stk[N];
int iout[N];
int ans = 0;
struct node
{
    
  int x, y;
  int r, w;
} a[N];
void add(int a, int b)
{
    
  e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u)
{
    
  dfn[u] = low[u] = ++timestamp;
  stk[++top] = u, in_stk[u] = true;
  for (int i = h[u]; ~i; i = ne[i])
  {
    
    int j = e[i];
    if (!dfn[j])
    {
    
      tarjan(j);
      low[u] = min(low[j], low[u]);
    }
    else if (in_stk[j])
      low[u] = min(low[u], dfn[j]);
  }
  if (dfn[u] == low[u])
  {
    
    ++scc_cnt;
    int y;
    do
    {
    
      y = stk[top--];
      in_stk[y] = false;
      id[y] = scc_cnt;
      //cout<<id[y]<<"--"<<scc_cnt<<"--"<<y<<endl;
      Size[scc_cnt]++;
      w[scc_cnt] = min(w[scc_cnt], a[y].w); //  The value of strongly connected components 
    } while (y != u);
  }
}
signed main()
{
    
  int t;
  scanf("%lld",&t);
  int cou=0;
  while (t--)
  {
    
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
      h[i] = -1;
    for (int i = 1; i <= n; i++)
      w[i] = 0x3f3f3f3f3f;
    for (int i = 1; i <= n; i++)
      in_stk[i] = false;
    for (int i = 1; i <= n; i++)
      iout[i] = 0;
    for(int i=1;i<=n;i++) dfn[i]=0;
    for(int i=1;i<=n;i++) low[i]=0;
    ans = 0;
    top = 0;
    idx = 0;
    scc_cnt = 0;
    for (int i = 1; i <= n; i++)
    {
    
      cin >> a[i].x >> a[i].y >> a[i].r >> a[i].w;
    }
    for (int i = 1; i <= n; i++)
    {
    
      for (int j = 1; j <= n; j++)
      {
    
        if(i==j) continue;
        int xx = (a[i].x - a[j].x) * (a[i].x - a[j].x);
        int yy = (a[i].y - a[j].y) * (a[i].y - a[j].y);
        if (xx + yy <= a[i].r * a[i].r) add(i, j);//printf("%lld %lld->\n",i,j);
      }
    }
    for (int i = 1; i <= n; i++)
    {
    
      if (!dfn[i]) tarjan(i);
    }
    //printf("%lld--%lld\n",id[4],id[5]);
    for (int i = 1; i <= n; i++)
    {
    
      for (int j = h[i]; ~j; j = ne[j])
      {
    
        int k = e[j];
        int x = id[k];
        int y = id[i];
        if (x != y) iout[x]++;
        //printf("%lld-->%lld",x,y);
      }
    }
    for (int i = 1; i <= scc_cnt; i++)
    {
    
      if (iout[i] == 0) ans += w[i];
    }
    printf("Case #%lld: %lld\n",++cou, ans);
  }
  return 0;
}

summary ： In this question , To sum up, even graphic problems are not necessarily done with geometry , When doing questions, it should be divergent thinking , Think about how to build a map , How to subtly transform the problem , After all, it is easier to solve the problem on a graph than in a two-dimensional plane . Another is that we should remember that a graph can be transformed into a directed acyclic graph after the strongly connected component shrinks , In this way, it becomes easier to solve problems .