Kvar_ispw17's blog
0%

HDU 5934 Bomb 题解

Posted on In

HDU 5934 Bomb 题解

题目大意

有 \(n\) 个炸弹， 每个点燃需要一定代价，每个炸弹有位置和爆炸半径，每次爆炸可以把周围在爆炸半径的炸弹引爆，并以此类推。求让所有炸弹全部爆炸的最小代价。

题解

我们对于炸弹 \(u\) 和 \(v\)，若 \(\rho(u,v)\leq \text{radis}(u)\)，则连一条有向边 \(u\to v\)。我们用 \(\text{tarjan}\) 得出图的强连通分量，把每个强连通分量缩成一个点，在新图上判断哪些“点”入度为 \(0\)，从该点开始起爆即可，注意缩点之后新点的代价是连通分量的最小代价（为了最终代价最小）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
// https://acm.hdu.edu.cn/showproblem.php?pid=5934
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;
typedef long long ll;
 
#define int ll

template <typename _Tp>
void read(_Tp &a, char c = 0, int f = 1) {
    for(c = getchar(); !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar()); a *= f;
}
 
template <typename _Tp>
void write(_Tp a) {
    if(a < 0) putchar('-'), a = -a;
    if(a > 9) write(a / 10); putchar(a % 10 + '0');
}

const int N = 1e3 + 5;
const int M = 1e6 + 5;

class Bomb {
public:
    int x, y, r, c;
    Bomb() {}
    Bomb(int _x, int _y, int _r, int _c) {
        x = _x;
        y = _y;
        r = _r;
        c = _c;
    }
} b[N];

int n, hd[N], nxt[M], to[M], tot, ind[N];

void add(int u, int v) {
    nxt[++tot] = hd[u] , to[hd[u] = tot] = v;
}

int dfn[N], low[N], idx;
int st[N], top, cnt, color[N], mn[N];
bool inq[N];

void tarjan(int p) { 
    dfn[p] = low[p] = ++idx;
    st[++top] = p;
    inq[p] = 1;
    for(int e = hd[p]; e; e = nxt[e]) {
        int v = to[e];
        if(!dfn[v]) {
            tarjan(v);
            low[p] = min(low[p], low[v]);
        } else if(inq[v]) {
            low[p] = min(low[p], dfn[v]);
        }
    }
    if(low[p] == dfn[p]) {
        int u;
        cnt++;
        do {
            u = st[top--];
            inq[u] = 0;
            mn[cnt] = min(mn[cnt], b[u].c);
            color[u] = cnt;
            // printf("%d ", u);
        } while(u != p);
        // printf("\n");
    }
}

inline void init() {
    tot = idx = top = cnt = 0;
    memset(inq, 0, sizeof inq);
    memset(hd, 0, sizeof hd);
    memset(nxt, 0, sizeof nxt);
    memset(to, 0, sizeof to);
    memset(ind, 0, sizeof ind);
    memset(color, 0, sizeof color);
    memset(dfn, 0, sizeof dfn);
    memset(low, 0, sizeof low);
    memset(mn, 0x3f, sizeof mn);
}

signed main() {
    // freopen("0725_1.in", "r", stdin);
    int T;
    read(T);
    for (int _T = 1; _T <= T; _T++) {
        init();
        read(n);
        for(int i = 1; i <= n; i++) {
            int x, y, r, c;
            read(x), read(y), read(r), read(c);
            b[i] = Bomb(x, y, r, c);
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == j) continue;
                double d = sqrt((b[i].x - b[j].x) * (b[i].x - b[j].x) + \
                                (b[i].y - b[j].y) * (b[i].y - b[j].y));
                if(d <= b[i].r) add(i, j);
            }
        }
        for(int i = 1; i <= n; i++) {
            if(!dfn[i]) tarjan(i);
        }
        for(int u = 1; u <= n; u++) {
            for(int e = hd[u]; e; e = nxt[e]) {
                int v = to[e];
                if(color[u] == color[v]) continue;
                ind[color[v]]++;
            }
        }
        ll ans = 0;
        for(int i = 1; i <= cnt; i++) {
            if(ind[i] == 0) {
                ans += mn[i];
            }
        }
        printf("Case #%d: %lld\n", _T, ans);
    }
    return 0;
}