UVa 11098 - Battle II

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

每個炸彈都有引爆範圍、炸彈半徑、以及炸彈所在座標。

  • 引爆一個炸彈時,其爆炸範圍內的其他炸彈也會被引爆,產生連鎖反應一次引爆多顆炸彈。
  • 引爆過的炸彈,無法再次引爆。
  • 引爆一個炸彈的成本與爆炸範圍成正比 1 : 1

求平均花費 (引爆總花費 / 引爆次數) 最小為何?

Sample Input

1
2
3
4
5
6
1
3
4 7 2 2
8 5 1 0
3 -3 1 1

Sample Output

1
Case #1: 1 0 2

Solution

問平均最少花費是有原因的,如果只問最少花費只需要引爆無法被連鎖的炸彈,或者在 SCC 連通元件中找一個花費最小的炸彈。

首先,在一個連鎖反應下,先做 SCC 進行縮點,知道一個 SCC 元件中用花費最小的那個炸彈代表即可,將圖轉換成 DAG 後。indegree = 0 的點必然需要手動引爆,在這樣的情況下,已經能讓所有炸彈引爆。

為了要讓平均花費最小,勢必增加引爆炸彈的數量,引爆時便能降低平均花費,但引爆的順序必須按照拓樸排序,否則會違反 引爆過的炸彈,無法再次引爆 的規則。

藉此,根據貪心策略,將非 indegree = 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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
// SCC, DAG, greedy
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAXN = 1024;
class SCC {
public:
int n;
vector<int> g[MAXN], dag[MAXN];
// <SCC begin>
int vfind[MAXN], findIdx;
int stk[MAXN], stkIdx;
int in_stk[MAXN], visited[MAXN];
int contract[MAXN];
int scc_cnt;
// <SCC end>
int scc(int u) {
in_stk[u] = visited[u] = 1;
stk[++stkIdx] = u, vfind[u] = ++findIdx;
int mn = vfind[u], v;
for(int i = 0; i < g[u].size(); i++) {
v = g[u][i];
if(!visited[v])
mn = min(mn, scc(v));
if(in_stk[v])
mn = min(mn, vfind[v]);
}
if(mn == vfind[u]) {
do {
in_stk[stk[stkIdx]] = 0;
contract[stk[stkIdx]] = scc_cnt;
} while(stk[stkIdx--] != u);
scc_cnt++;
}
return mn;
}
void addEdge(int u, int v) { // u -> v
g[u].push_back(v);
}
void solve() {
for (int i = 0; i < n; i++)
visited[i] = in_stk[i] = 0;
scc_cnt = 0;
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
stkIdx = findIdx = 0;
scc(i);
}
}
void make_DAG() {
int x, y;
for (int i = 0; i < n; i++) {
x = contract[i];
for (int j = 0; j < g[i].size(); j++) {
y = contract[g[i][j]];
if (x != y)
dag[x].push_back(y);
}
}
for (int i = 0; i < scc_cnt; i++) {
sort(dag[i].begin(), dag[i].end());
dag[i].resize(unique(dag[i].begin(), dag[i].end()) - dag[i].begin());
}
}
void init(int n) {
this->n = n;
for (int i = 0; i < n; i++)
g[i].clear(), dag[i].clear();
}
} g;
int X[MAXN], Y[MAXN], E[MAXN], R[MAXN];
void greedy() {
int m = g.scc_cnt, n = g.n;
int cost[MAXN], scc_id[MAXN], pick[MAXN] = {};
for (int i = 0; i < m; i++)
cost[i] = 0x3f3f3f3f, scc_id[i] = -1;
for (int i = 0; i < n; i++) {
if (cost[g.contract[i]] > E[i])
cost[g.contract[i]] = E[i], scc_id[g.contract[i]] = i;
}
int indeg[MAXN] = {};
vector<int> topo;
queue<int> Q;
for (int i = 0; i < m; i++) {
for (int j = 0; j < g.dag[i].size(); j++) {
indeg[g.dag[i][j]]++;
}
}
// greedy, let reta / retb = minimum value
// if (reta / retb) > (reta + cost) / (retb + 1)
long long reta = 0, retb = 0; // min average cost = total cost / #bomb
vector< pair<int, int> > candidate;
for (int i = 0; i < m; i++) {
if (indeg[i] == 0) {
reta += cost[i], retb++;
pick[i] = 1;
} else {
candidate.push_back(make_pair(cost[i], i));
}
}
sort(candidate.begin(), candidate.end());
for (int i = 0; i < candidate.size(); i++) {
long long c = candidate[i].first;
if (reta * (retb + 1) > (reta + c) * retb) {
reta += c, retb++;
pick[candidate[i].second] = 1;
}
}
// topo
for (int i = 0; i < m; i++)
if (indeg[i] == 0) Q.push(i);
while (!Q.empty()) {
int u = Q.front(), v;
Q.pop();
topo.push_back(u);
for (int i = 0; i < g.dag[u].size(); i++) {
v = g.dag[u][i];
if (--indeg[v] == 0)
Q.push(v);
}
}
// make order with fire rule
int topo_r[MAXN] = {};
vector< pair<int, int> > ret;
for (int i = 0; i < topo.size(); i++) {
topo_r[topo[i]] = i;
}
for (int i = 0; i < m; i++) {
if (pick[i])
ret.push_back(make_pair(topo_r[i], scc_id[i]));
}
sort(ret.begin(), ret.end());
for (int i = ret.size() - 1; i >= 0; i--)
printf(" %d", ret[i].second);
puts("");
// printf("%lld / %lld\n", reta, retb);
}
int main() {
int testcase, cases = 0;
int n;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d %d %d %d", &X[i], &Y[i], &R[i], &E[i]);
g.init(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)
continue;
long long dist = (long long)(X[i] - X[j]) * (X[i] - X[j]) + (long long)(Y[i] - Y[j]) * (Y[i] - Y[j]);
long long r = (long long)(R[i] + E[i] + R[j]) * (R[i] + E[i] + R[j]);
if (dist <= r)
g.addEdge(i, j);
}
}
g.solve();
g.make_DAG();
printf("Case #%d:", ++cases);
greedy();
}
return 0;
}
/*
1
3
4 7 2 2
8 5 1 0
3 -3 1 1
1
7
24 1 4 7
38 33 4 3
13 13 2 0
34 1 0 0
6 25 5 4
1 14 3 7
30 35 1 6
*/